<?xml version="1.0" encoding="utf-8"?>
<!DOCTYPE html>
<html xmlns="http://www.w3.org/1999/xhtml" xmlns:epub="http://www.idpf.org/2007/ops" xml:lang="en" lang="en">
<!-- Created by GNU Texinfo 5.1, http://www.gnu.org/software/texinfo/ -->
<head>
<title>Structure and Interpretation of Computer Programs, 2e: 4.1</title>

<meta name="description" content="Structure and Interpretation of Computer Programs, 2e: 4.1" />
<meta name="keywords" content="Structure and Interpretation of Computer Programs, 2e: 4.1" />
<meta name="viewport" content="width=device-width, initial-scale=1.0" />
<meta name="Generator" content="texi2any" />
<meta charset="utf-8" />
<link href="index.xhtml#Top" rel="start" title="Top" />
<link href="Term-Index.xhtml#Term-Index" rel="index" title="Term Index" />
<link href="index.xhtml#SEC_Contents" rel="contents" title="Table of Contents" />
<link href="Chapter-4.xhtml#Chapter-4" rel="prev" title="Chapter 4" />
<link href="4_002e2.xhtml#g_t4_002e2" rel="next" title="4.2" />
<link href="Chapter-4.xhtml#Chapter-4" rel="prev" title="Chapter 4" />

<link href="css/style.css" rel="stylesheet" type="text/css" />
<link href="css/prettify.css" rel="stylesheet" type="text/css" />
</head>

<body>
<section><span class="top jump" title="Jump to top"><a href="#pagetop" accesskey="t">⇡</a></span><a id="pagetop"></a><a id="g_t4_002e1"></a>
<nav class="header">
<p>
Next: <a href="4_002e2.xhtml#g_t4_002e2" accesskey="n" rel="next">4.2</a>, Prev: <a href="Chapter-4.xhtml#Chapter-4" accesskey="p" rel="prev">Chapter 4</a>, Up: <a href="Chapter-4.xhtml#Chapter-4" accesskey="u" rel="prev">Chapter 4</a>   [<a href="index.xhtml#SEC_Contents" title="Table of contents" accesskey="c" rel="contents">Contents</a>]</p>
</nav>
<a id="The-Metacircular-Evaluator"></a>
<h3 class="section"><span class="secnum">4.1</span><span class="sectitle">The Metacircular Evaluator</span></h3>

<p>Our evaluator for Lisp will be implemented as a Lisp program.  It may seem
circular to think about evaluating Lisp programs using an evaluator that is
itself implemented in Lisp.  However, evaluation is a process, so it is
appropriate to describe the evaluation process using Lisp, which, after all, is
our tool for describing processes.<a class="footnote_link" id="DOCF207" href="#FOOT207"><sup>207</sup></a>
An evaluator that is written in the same language that it evaluates is said to
be <a id="index-metacircular"></a>
<em>metacircular</em>.
</p>
<p>The metacircular evaluator is essentially a Scheme formulation of the
environment model of evaluation described in <a href="3_002e2.xhtml#g_t3_002e2">3.2</a>.  Recall that
the model has two basic parts:
</p>
<ol>
<li> To evaluate a combination (a compound expression other than a special form),
evaluate the subexpressions and then apply the value of the operator
subexpression to the values of the operand subexpressions.

</li><li> To apply a compound procedure to a set of arguments, evaluate the body of the
procedure in a new environment.  To construct this environment, extend the
environment part of the procedure object by a frame in which the formal
parameters of the procedure are bound to the arguments to which the procedure
is applied.

</li></ol>

<p>These two rules describe the essence of the evaluation process, a basic cycle
in which expressions to be evaluated in environments are reduced to procedures
to be applied to arguments, which in turn are reduced to new expressions to be
evaluated in new environments, and so on, until we get down to symbols, whose
values are looked up in the environment, and to primitive procedures, which are
applied directly (see <a href="#Figure-4_002e1">Figure 4.1</a>).<a class="footnote_link" id="DOCF208" href="#FOOT208"><sup>208</sup></a> 
This evaluation cycle will be embodied by the interplay between the two
critical procedures in the evaluator, <code>eval</code> and <code>apply</code>, which are
described in <a href="#g_t4_002e1_002e1">4.1.1</a> (see <a href="#Figure-4_002e1">Figure 4.1</a>).
</p>
<figure class="float">
<a id="Figure-4_002e1"></a>
<object style="width: 60.35ex; height: 24.52ex;" data="fig/chap4/Fig4.1a.std.svg" type="image/svg+xml">SVG</object>

<figcaption class="float-caption">
<p><strong>Figure 4.1:</strong> The <code>eval</code>-<code>apply</code> cycle exposes the essence of a computer language.</p>
</figcaption>
</figure>

<p>The implementation of the evaluator will depend upon procedures that define the
<a id="index-syntax"></a>
<em>syntax</em> of the expressions to be evaluated.  We will use data
abstraction to make the evaluator independent of the representation of the
language.  For example, rather than committing to a choice that an assignment
is to be represented by a list beginning with the symbol <code>set!</code> we use an
abstract predicate <code>assignment?</code> to test for an assignment, and we use
abstract selectors <code>assignment-variable</code> and <code>assignment-value</code> to
access the parts of an assignment.  Implementation of expressions will be
described in detail in <a href="#g_t4_002e1_002e2">4.1.2</a>.  There are also operations,
described in <a href="#g_t4_002e1_002e3">4.1.3</a>, that specify the representation of procedures
and environments.  For example, <code>make-procedure</code> constructs compound
procedures, <code>lookup-variable-value</code> accesses the values of variables, and
<code>apply-primitive-procedure</code> applies a primitive procedure to a given list
of arguments.
</p>

<a id="g_t4_002e1_002e1"></a>
<a id="The-Core-of-the-Evaluator"></a>
<h4 class="subsection"><span class="secnum">4.1.1</span><span class="sectitle">The Core of the Evaluator</span></h4>

<p>The evaluation process can be described as the interplay between two
procedures: <code>eval</code> and <code>apply</code>.
</p>
<a id="Eval"></a>
<h5 class="subsubheading">Eval</h5>

<p><code>Eval</code> takes as arguments an expression and an environment.  It classifies
the expression and directs its evaluation.  <code>Eval</code> is structured as a case
analysis of the syntactic type of the expression to be evaluated.  In order to
keep the procedure general, we express the determination of the type of an
expression abstractly, making no commitment to any particular representation
for the various types of expressions.  Each type of expression has a predicate
that tests for it and an abstract means for selecting its parts.  This
<a id="index-abstract-syntax"></a>
<em>abstract syntax</em> makes it easy to see how we can change the syntax of
the language by using the same evaluator, but with a different collection of
syntax procedures.
</p>
<p><b>Primitive expressions</b>
</p>
<ul>
<li> For self-evaluating expressions, such as numbers, <code>eval</code> returns the
expression itself.

</li><li> <code>Eval</code> must look up variables in the environment to find their values.

</li></ul>

<p><b>Special forms</b>
</p>
<ul>
<li> For quoted expressions, <code>eval</code> returns the expression that was quoted.

</li><li> An assignment to (or a definition of) a variable must recursively call
<code>eval</code> to compute the new value to be associated with the variable.  The
environment must be modified to change (or create) the binding of the variable.

</li><li> An <code>if</code> expression requires special processing of its parts, so as to
evaluate the consequent if the predicate is true, and otherwise to evaluate the
alternative.

</li><li> A <code>lambda</code> expression must be transformed into an applicable procedure by
packaging together the parameters and body specified by the <code>lambda</code>
expression with the environment of the evaluation.

</li><li> A <code>begin</code> expression requires evaluating its sequence of expressions in
the order in which they appear.

</li><li> A case analysis (<code>cond</code>) is transformed into a nest of <code>if</code>
expressions and then evaluated.

</li></ul>

<p><b>Combinations</b>
</p>
<ul>
<li> For a procedure application, <code>eval</code> must recursively evaluate the operator
part and the operands of the combination.  The resulting procedure and
arguments are passed to <code>apply</code>, which handles the actual procedure
application.

</li></ul>

<p>Here is the definition of <code>eval</code>:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">eval exp env</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">cond</span><span class="pln"> </span><span class="opn">((</span><span class="pln">self-evaluating? exp</span><span class="clo">)</span><span class="pln"> 
         exp</span><span class="clo">)</span><span class="pln">
        </span><span class="opn">((</span><span class="pln">variable? exp</span><span class="clo">)</span><span class="pln"> 
         </span><span class="opn">(</span><span class="pln">lookup-variable-value exp env</span><span class="clo">))</span><span class="pln">
        </span><span class="opn">((</span><span class="pln">quoted? exp</span><span class="clo">)</span><span class="pln"> 
         </span><span class="opn">(</span><span class="pln">text-of-quotation exp</span><span class="clo">))</span><span class="pln">
        </span><span class="opn">((</span><span class="pln">assignment? exp</span><span class="clo">)</span><span class="pln"> 
         </span><span class="opn">(</span><span class="pln">eval-assignment exp env</span><span class="clo">))</span><span class="pln">
        </span><span class="opn">((</span><span class="pln">definition? exp</span><span class="clo">)</span><span class="pln"> 
         </span><span class="opn">(</span><span class="pln">eval-definition exp env</span><span class="clo">))</span><span class="pln">
        </span><span class="opn">((</span><span class="kwd">if</span><span class="pun">?</span><span class="pln"> exp</span><span class="clo">)</span><span class="pln"> 
         </span><span class="opn">(</span><span class="pln">eval-if exp env</span><span class="clo">))</span><span class="pln">
        </span><span class="opn">((</span><span class="kwd">lambda</span><span class="pun">?</span><span class="pln"> exp</span><span class="clo">)</span><span class="pln">
         </span><span class="opn">(</span><span class="pln">make-procedure 
          </span><span class="opn">(</span><span class="pln">lambda-parameters exp</span><span class="clo">)</span><span class="pln">
          </span><span class="opn">(</span><span class="pln">lambda-body exp</span><span class="clo">)</span><span class="pln">
          env</span><span class="clo">))</span><span class="pln">
        </span><span class="opn">((</span><span class="kwd">begin</span><span class="pun">?</span><span class="pln"> exp</span><span class="clo">)</span><span class="pln">
         </span><span class="opn">(</span><span class="pln">eval-sequence 
          </span><span class="opn">(</span><span class="pln">begin-actions exp</span><span class="clo">)</span><span class="pln"> 
          env</span><span class="clo">))</span><span class="pln">
        </span><span class="opn">((</span><span class="kwd">cond</span><span class="pun">?</span><span class="pln"> exp</span><span class="clo">)</span><span class="pln"> 
         </span><span class="opn">(</span><span class="pln">eval </span><span class="opn">(</span><span class="pln">cond-</span><span class="pun">&gt;</span><span class="kwd">if</span><span class="pln"> exp</span><span class="clo">)</span><span class="pln"> env</span><span class="clo">))</span><span class="pln">
        </span><span class="opn">((</span><span class="pln">application? exp</span><span class="clo">)</span><span class="pln">
         </span><span class="opn">(</span><span class="pln">apply </span><span class="opn">(</span><span class="pln">eval </span><span class="opn">(</span><span class="pln">operator exp</span><span class="clo">)</span><span class="pln"> env</span><span class="clo">)</span><span class="pln">
                </span><span class="opn">(</span><span class="pln">list-of-values 
                 </span><span class="opn">(</span><span class="pln">operands exp</span><span class="clo">)</span><span class="pln"> 
                 env</span><span class="clo">)))</span><span class="pln">
        </span><span class="opn">(</span><span class="kwd">else</span><span class="pln">
         </span><span class="opn">(</span><span class="err">error</span><span class="pln"> </span><span class="str">"Unknown expression 
                 type: EVAL"</span><span class="pln"> exp</span><span class="clo">))))</span></pre></div>

<p>For clarity, <code>eval</code> has been implemented as a case analysis using
<code>cond</code>.  The disadvantage of this is that our procedure handles only a few
distinguishable types of expressions, and no new ones can be defined without
editing the definition of <code>eval</code>.  In most Lisp implementations,
dispatching on the type of an expression is done in a data-directed style.
This allows a user to add new types of expressions that <code>eval</code> can
distinguish, without modifying the definition of <code>eval</code> itself.  (See
<a href="#Exercise-4_002e3">Exercise 4.3</a>.)
</p>
<a id="Apply"></a>
<h5 class="subsubheading">Apply</h5>

<p><code>Apply</code> takes two arguments, a procedure and a list of arguments to which
the procedure should be applied.  <code>Apply</code> classifies procedures into two
kinds: It calls <code>apply-primitive-procedure</code> to apply primitives; it
applies compound procedures by sequentially evaluating the expressions that
make up the body of the procedure.  The environment for the evaluation of the
body of a compound procedure is constructed by extending the base environment
carried by the procedure to include a frame that binds the parameters of the
procedure to the arguments to which the procedure is to be applied.  Here is
the definition of <code>apply</code>:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">apply procedure arguments</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">cond</span><span class="pln"> </span><span class="opn">((</span><span class="pln">primitive-procedure? procedure</span><span class="clo">)</span><span class="pln">
         </span><span class="opn">(</span><span class="pln">apply-primitive-procedure 
          procedure 
          arguments</span><span class="clo">))</span><span class="pln">
        </span><span class="opn">((</span><span class="pln">compound-procedure? procedure</span><span class="clo">)</span><span class="pln">
         </span><span class="opn">(</span><span class="pln">eval-sequence
           </span><span class="opn">(</span><span class="pln">procedure-body procedure</span><span class="clo">)</span><span class="pln">
           </span><span class="opn">(</span><span class="pln">extend-environment
             </span><span class="opn">(</span><span class="pln">procedure-parameters 
              procedure</span><span class="clo">)</span><span class="pln">
             arguments
             </span><span class="opn">(</span><span class="pln">procedure-environment 
              procedure</span><span class="clo">))))</span><span class="pln">
        </span><span class="opn">(</span><span class="kwd">else</span><span class="pln">
         </span><span class="opn">(</span><span class="err">error</span><span class="pln"> </span><span class="str">"Unknown procedure 
                 type: APPLY"</span><span class="pln"> 
                procedure</span><span class="clo">))))</span></pre></div>

<a id="Procedure-arguments"></a>
<h5 class="subsubheading">Procedure arguments</h5>

<p>When <code>eval</code> processes a procedure application, it uses
<code>list-of-values</code> to produce the list of arguments to which the procedure
is to be applied. <code>List-of-values</code> takes as an argument the operands of
the combination.  It evaluates each operand and returns a list of the
corresponding values:<a class="footnote_link" id="DOCF209" href="#FOOT209"><sup>209</sup></a>
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">list-of-values exps env</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="pln">no-operands? exps</span><span class="clo">)</span><span class="pln">
      </span><span class="lit">'</span><span class="opn">(</span><span class="clo">)</span><span class="pln">
      </span><span class="opn">(</span><span class="kwd">cons</span><span class="pln"> </span><span class="opn">(</span><span class="pln">eval </span><span class="opn">(</span><span class="pln">first-operand exps</span><span class="clo">)</span><span class="pln"> env</span><span class="clo">)</span><span class="pln">
            </span><span class="opn">(</span><span class="pln">list-of-values 
             </span><span class="opn">(</span><span class="pln">rest-operands exps</span><span class="clo">)</span><span class="pln"> 
             env</span><span class="clo">))))</span></pre></div>

<a id="Conditionals"></a>
<h5 class="subsubheading">Conditionals</h5>

<p><code>Eval-if</code> evaluates the predicate part of an <code>if</code> expression in the
given environment.  If the result is true, <code>eval-if</code> evaluates the
consequent, otherwise it evaluates the alternative:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">eval-if exp env</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="pln">true? </span><span class="opn">(</span><span class="pln">eval </span><span class="opn">(</span><span class="pln">if-predicate exp</span><span class="clo">)</span><span class="pln"> env</span><span class="clo">))</span><span class="pln">
      </span><span class="opn">(</span><span class="pln">eval </span><span class="opn">(</span><span class="pln">if-consequent exp</span><span class="clo">)</span><span class="pln"> env</span><span class="clo">)</span><span class="pln">
      </span><span class="opn">(</span><span class="pln">eval </span><span class="opn">(</span><span class="pln">if-alternative exp</span><span class="clo">)</span><span class="pln"> env</span><span class="clo">)))</span></pre></div>

<p>The use of <code>true?</code> in <code>eval-if</code> highlights the issue of the
connection between an implemented language and an implementation language.  The
<code>if-predicate</code> is evaluated in the language being implemented and thus
yields a value in that language.  The interpreter predicate <code>true?</code>
translates that value into a value that can be tested by the <code>if</code> in the
implementation language: The metacircular representation of truth might not be
the same as that of the underlying Scheme.<a class="footnote_link" id="DOCF210" href="#FOOT210"><sup>210</sup></a>
</p>
<a id="Sequences"></a>
<h5 class="subsubheading">Sequences</h5>

<p><code>Eval-sequence</code> is used by <code>apply</code> to evaluate the sequence of
expressions in a procedure body and by <code>eval</code> to evaluate the sequence of
expressions in a <code>begin</code> expression.  It takes as arguments a sequence of
expressions and an environment, and evaluates the expressions in the order in
which they occur.  The value returned is the value of the final expression.
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">eval-sequence exps env</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">cond</span><span class="pln"> </span><span class="opn">((</span><span class="pln">last-exp? exps</span><span class="clo">)</span><span class="pln"> 
         </span><span class="opn">(</span><span class="pln">eval </span><span class="opn">(</span><span class="pln">first-exp exps</span><span class="clo">)</span><span class="pln"> env</span><span class="clo">))</span><span class="pln">
        </span><span class="opn">(</span><span class="kwd">else</span><span class="pln"> 
         </span><span class="opn">(</span><span class="pln">eval </span><span class="opn">(</span><span class="pln">first-exp exps</span><span class="clo">)</span><span class="pln"> env</span><span class="clo">)</span><span class="pln">
         </span><span class="opn">(</span><span class="pln">eval-sequence </span><span class="opn">(</span><span class="pln">rest-exps exps</span><span class="clo">)</span><span class="pln"> 
                        env</span><span class="clo">))))</span></pre></div>

<a id="Assignments-and-definitions"></a>
<h5 class="subsubheading">Assignments and definitions</h5>

<p>The following procedure handles assignments to variables.  It calls <code>eval</code>
to find the value to be assigned and transmits the variable and the resulting
value to <code>set-variable-value!</code> to be installed in the designated
environment.
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">eval-assignment exp env</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">set-variable-value! 
   </span><span class="opn">(</span><span class="pln">assignment-variable exp</span><span class="clo">)</span><span class="pln">
   </span><span class="opn">(</span><span class="pln">eval </span><span class="opn">(</span><span class="pln">assignment-value exp</span><span class="clo">)</span><span class="pln"> env</span><span class="clo">)</span><span class="pln">
   env</span><span class="clo">)</span><span class="pln">
  </span><span class="lit">'ok</span><span class="clo">)</span></pre></div>

<p>Definitions of variables are handled in a similar manner.<a class="footnote_link" id="DOCF211" href="#FOOT211"><sup>211</sup></a>
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">eval-definition exp env</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">define-variable! 
    </span><span class="opn">(</span><span class="pln">definition-variable exp</span><span class="clo">)</span><span class="pln">
    </span><span class="opn">(</span><span class="pln">eval </span><span class="opn">(</span><span class="pln">definition-value exp</span><span class="clo">)</span><span class="pln"> env</span><span class="clo">)</span><span class="pln">
    env</span><span class="clo">)</span><span class="pln">
  </span><span class="lit">'ok</span><span class="clo">)</span></pre></div>

<p>We have chosen here to return the symbol <code>ok</code> as the value of an
assignment or a definition.<a class="footnote_link" id="DOCF212" href="#FOOT212"><sup>212</sup></a>
</p>
<blockquote>
<p><strong><a id="Exercise-4_002e1"></a>Exercise 4.1:</strong> Notice that we cannot tell whether
the metacircular evaluator evaluates operands from left to right or from right
to left.  Its evaluation order is inherited from the underlying Lisp: If the
arguments to <code>cons</code> in <code>list-of-values</code> are evaluated from left to
right, then <code>list-of-values</code> will evaluate operands from left to right;
and if the arguments to <code>cons</code> are evaluated from right to left, then
<code>list-of-values</code> will evaluate operands from right to left.
</p>
<p>Write a version of <code>list-of-values</code> that evaluates operands from left to
right regardless of the order of evaluation in the underlying Lisp.  Also write
a version of <code>list-of-values</code> that evaluates operands from right to left.
</p></blockquote>

<a id="g_t4_002e1_002e2"></a>
<a id="Representing-Expressions"></a>
<h4 class="subsection"><span class="secnum">4.1.2</span><span class="sectitle">Representing Expressions</span></h4>

<p>The evaluator is reminiscent of the symbolic differentiation program discussed
in <a href="2_002e3.xhtml#g_t2_002e3_002e2">2.3.2</a>.  Both programs operate on symbolic expressions.  In
both programs, the result of operating on a compound expression is determined
by operating recursively on the pieces of the expression and combining the
results in a way that depends on the type of the expression.  In both programs
we used data abstraction to decouple the general rules of operation from the
details of how expressions are represented.  In the differentiation program
this meant that the same differentiation procedure could deal with algebraic
expressions in prefix form, in infix form, or in some other form.  For the
evaluator, this means that the syntax of the language being evaluated is
determined solely by the procedures that classify and extract pieces of
expressions.
</p>
<p>Here is the specification of the syntax of our language:
</p>
<ul>
<li> The only self-evaluating items are numbers and strings:

<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">self-evaluating? exp</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">cond</span><span class="pln"> </span><span class="opn">((</span><span class="pln">number? exp</span><span class="clo">)</span><span class="pln"> true</span><span class="clo">)</span><span class="pln">
        </span><span class="opn">((</span><span class="pln">string? exp</span><span class="clo">)</span><span class="pln"> true</span><span class="clo">)</span><span class="pln">
        </span><span class="opn">(</span><span class="kwd">else</span><span class="pln"> false</span><span class="clo">)))</span></pre></div>

</li><li> Variables are represented by symbols:

<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">variable? exp</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">symbol? exp</span><span class="clo">))</span></pre></div>

</li><li> Quotations have the form <code>(quote ⟨<var>text-of-quotation</var>⟩)</code>:<a class="footnote_link" id="DOCF213" href="#FOOT213"><sup>213</sup></a>

<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">quoted? exp</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">tagged-list? exp </span><span class="lit">'quote</span><span class="clo">))</span><span class="pln">

</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">text-of-quotation exp</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">cadr</span><span class="pln"> exp</span><span class="clo">))</span></pre></div>

<p><code>Quoted?</code> is defined in terms of the procedure <code>tagged-list?</code>, which
identifies lists beginning with a designated symbol:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">tagged-list? exp tag</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="pln">pair? exp</span><span class="clo">)</span><span class="pln">
      </span><span class="opn">(</span><span class="kwd">eq</span><span class="pun">?</span><span class="pln"> </span><span class="opn">(</span><span class="kwd">car</span><span class="pln"> exp</span><span class="clo">)</span><span class="pln"> tag</span><span class="clo">)</span><span class="pln">
      false</span><span class="clo">))</span></pre></div>

</li><li> Assignments have the form <code>(set! ⟨<var>var</var>⟩ ⟨<var>value</var>⟩)</code>:

<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">assignment? exp</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">tagged-list? exp </span><span class="lit">'set!</span><span class="clo">))</span><span class="pln">

</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">assignment-variable exp</span><span class="clo">)</span><span class="pln"> 
  </span><span class="opn">(</span><span class="kwd">cadr</span><span class="pln"> exp</span><span class="clo">))</span><span class="pln">

</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">assignment-value exp</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="kwd">caddr</span><span class="pln"> exp</span><span class="clo">))</span></pre></div>

</li><li> Definitions have the form

<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> ⟨</span><var><span class="pln">var</span></var><span class="pln">⟩ ⟨</span><var><span class="pln">value</span></var><span class="pln">⟩</span><span class="clo">)</span></pre></div>

<p>or the form
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">⟨</span><var><span class="pln">var</span></var><span class="pln">⟩ ⟨</span><var><span class="pln">param</span><span class="pun">₁</span></var><span class="pln">⟩ </span><span class="roman"><span class="pun">…</span></span><span class="pln"> ⟨</span><var><span class="pln">param</span><span class="pun">ₙ</span></var><span class="pln">⟩</span><span class="clo">)</span><span class="pln">
  ⟨</span><var><span class="pln">body</span></var><span class="pln">⟩</span><span class="clo">)</span></pre></div>

<p>The latter form (standard procedure definition) is syntactic sugar for
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> ⟨</span><var><span class="pln">var</span></var><span class="pln">⟩
  </span><span class="opn">(</span><span class="kwd">lambda</span><span class="pln"> </span><span class="opn">(</span><span class="pln">⟨</span><var><span class="pln">param</span><span class="pun">₁</span></var><span class="pln">⟩ </span><span class="roman"><span class="pun">…</span></span><span class="pln"> ⟨</span><var><span class="pln">param</span><span class="pun">ₙ</span></var><span class="pln">⟩</span><span class="clo">)</span><span class="pln">
    ⟨</span><var><span class="pln">body</span></var><span class="pln">⟩</span><span class="clo">))</span></pre></div>

<p>The corresponding syntax procedures are the following:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">definition? exp</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">tagged-list? exp </span><span class="lit">'define</span><span class="clo">))</span><span class="pln">

</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">definition-variable exp</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="pln">symbol? </span><span class="opn">(</span><span class="kwd">cadr</span><span class="pln"> exp</span><span class="clo">))</span><span class="pln">
      </span><span class="opn">(</span><span class="kwd">cadr</span><span class="pln"> exp</span><span class="clo">)</span><span class="pln">
      </span><span class="opn">(</span><span class="kwd">caadr</span><span class="pln"> exp</span><span class="clo">)))</span><span class="pln">

</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">definition-value exp</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="pln">symbol? </span><span class="opn">(</span><span class="kwd">cadr</span><span class="pln"> exp</span><span class="clo">))</span><span class="pln">
      </span><span class="opn">(</span><span class="kwd">caddr</span><span class="pln"> exp</span><span class="clo">)</span><span class="pln">
      </span><span class="opn">(</span><span class="pln">make-lambda 
       </span><span class="opn">(</span><span class="kwd">cdadr</span><span class="pln"> exp</span><span class="clo">)</span><span class="pln">   </span><span class="roman"><span class="com">; formal parameters</span></span><span class="pln">
       </span><span class="opn">(</span><span class="kwd">cddr</span><span class="pln"> exp</span><span class="clo">))))</span><span class="pln"> </span><span class="roman"><span class="com">; body</span></span>
</pre></div>

</li><li> <code>Lambda</code> expressions are lists that begin with the symbol <code>lambda</code>:

<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="kwd">lambda</span><span class="pun">?</span><span class="pln"> exp</span><span class="clo">)</span><span class="pln"> 
  </span><span class="opn">(</span><span class="pln">tagged-list? exp </span><span class="lit">'lambda</span><span class="clo">))</span><span class="pln">
</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">lambda-parameters exp</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="kwd">cadr</span><span class="pln"> exp</span><span class="clo">))</span><span class="pln">
</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">lambda-body exp</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="kwd">cddr</span><span class="pln"> exp</span><span class="clo">))</span></pre></div>

<p>We also provide a constructor for <code>lambda</code> expressions, which is used by
<code>definition-value</code>, above:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">make-lambda parameters body</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">cons</span><span class="pln"> </span><span class="lit">'lambda</span><span class="pln"> </span><span class="opn">(</span><span class="kwd">cons</span><span class="pln"> parameters body</span><span class="clo">)))</span></pre></div>

</li><li> Conditionals begin with <code>if</code> and have a predicate, a consequent, and an
(optional) alternative.  If the expression has no alternative part, we provide
<code>false</code> as the alternative.<a class="footnote_link" id="DOCF214" href="#FOOT214"><sup>214</sup></a>

<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="kwd">if</span><span class="pun">?</span><span class="pln"> exp</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">tagged-list? exp </span><span class="lit">'if</span><span class="clo">))</span><span class="pln">
</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">if-predicate exp</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="kwd">cadr</span><span class="pln"> exp</span><span class="clo">))</span><span class="pln">
</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">if-consequent exp</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="kwd">caddr</span><span class="pln"> exp</span><span class="clo">))</span><span class="pln">
</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">if-alternative exp</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="pln">not </span><span class="opn">(</span><span class="pln">null? </span><span class="opn">(</span><span class="kwd">cdddr</span><span class="pln"> exp</span><span class="clo">)))</span><span class="pln">
      </span><span class="opn">(</span><span class="kwd">cadddr</span><span class="pln"> exp</span><span class="clo">)</span><span class="pln">
      </span><span class="lit">'false</span><span class="clo">))</span></pre></div>

<p>We also provide a constructor for <code>if</code> expressions, to be used by
<code>cond-&gt;if</code> to transform <code>cond</code> expressions into <code>if</code>
expressions:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">make-if predicate 
                 consequent 
                 alternative</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">list </span><span class="lit">'if</span><span class="pln"> 
        predicate 
        consequent 
        alternative</span><span class="clo">))</span></pre></div>

</li><li> <code>Begin</code> packages a sequence of expressions into a single expression.  We
include syntax operations on <code>begin</code> expressions to extract the actual
sequence from the <code>begin</code> expression, as well as selectors that return the
first expression and the rest of the expressions in the
sequence.<a class="footnote_link" id="DOCF215" href="#FOOT215"><sup>215</sup></a>

<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="kwd">begin</span><span class="pun">?</span><span class="pln"> exp</span><span class="clo">)</span><span class="pln"> 
  </span><span class="opn">(</span><span class="pln">tagged-list? exp </span><span class="lit">'begin</span><span class="clo">))</span><span class="pln">
</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">begin-actions exp</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="kwd">cdr</span><span class="pln"> exp</span><span class="clo">))</span><span class="pln">
</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">last-exp? seq</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">null? </span><span class="opn">(</span><span class="kwd">cdr</span><span class="pln"> seq</span><span class="clo">)))</span><span class="pln">
</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">first-exp seq</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="kwd">car</span><span class="pln"> seq</span><span class="clo">))</span><span class="pln">
</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">rest-exps seq</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="kwd">cdr</span><span class="pln"> seq</span><span class="clo">))</span></pre></div>

<p>We also include a constructor <code>sequence-&gt;exp</code> (for use by <code>cond-&gt;if</code>)
that transforms a sequence into a single expression, using <code>begin</code> if
necessary:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">sequence-</span><span class="pun">&gt;</span><span class="pln">exp seq</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">cond</span><span class="pln"> </span><span class="opn">((</span><span class="pln">null? seq</span><span class="clo">)</span><span class="pln"> seq</span><span class="clo">)</span><span class="pln">
        </span><span class="opn">((</span><span class="pln">last-exp? seq</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">first-exp seq</span><span class="clo">))</span><span class="pln">
        </span><span class="opn">(</span><span class="kwd">else</span><span class="pln"> </span><span class="opn">(</span><span class="pln">make-begin seq</span><span class="clo">))))</span><span class="pln">

</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">make-begin seq</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="kwd">cons</span><span class="pln"> </span><span class="lit">'begin</span><span class="pln"> seq</span><span class="clo">))</span></pre></div>

</li><li> A procedure application is any compound expression that is not one of the above
expression types.  The <code>car</code> of the expression is the operator, and the
<code>cdr</code> is the list of operands:

<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">application? exp</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">pair? exp</span><span class="clo">))</span><span class="pln">
</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">operator exp</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="kwd">car</span><span class="pln"> exp</span><span class="clo">))</span><span class="pln">
</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">operands exp</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="kwd">cdr</span><span class="pln"> exp</span><span class="clo">))</span><span class="pln">
</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">no-operands? ops</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">null? ops</span><span class="clo">))</span><span class="pln">
</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">first-operand ops</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="kwd">car</span><span class="pln"> ops</span><span class="clo">))</span><span class="pln">
</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">rest-operands ops</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="kwd">cdr</span><span class="pln"> ops</span><span class="clo">))</span></pre></div>

</li></ul>

<a id="Derived-expressions"></a>
<h5 class="subsubheading">Derived expressions</h5>

<p>Some special forms in our language can be defined in terms of expressions
involving other special forms, rather than being implemented directly.  One
example is <code>cond</code>, which can be implemented as a nest of <code>if</code>
expressions.  For example, we can reduce the problem of evaluating the
expression
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">cond</span><span class="pln"> </span><span class="opn">((</span><span class="pun">&gt;</span><span class="pln"> x </span><span class="lit">0</span><span class="clo">)</span><span class="pln"> x</span><span class="clo">)</span><span class="pln">
      </span><span class="opn">((</span><span class="pun">=</span><span class="pln"> x </span><span class="lit">0</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">display </span><span class="lit">'zero</span><span class="clo">)</span><span class="pln"> </span><span class="lit">0</span><span class="clo">)</span><span class="pln">
      </span><span class="opn">(</span><span class="kwd">else</span><span class="pln"> </span><span class="opn">(</span><span class="pun">-</span><span class="pln"> x</span><span class="clo">)))</span></pre></div>

<p>to the problem of evaluating the following expression involving <code>if</code> and
<code>begin</code> expressions:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="pun">&gt;</span><span class="pln"> x </span><span class="lit">0</span><span class="clo">)</span><span class="pln">
    x
    </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="pun">=</span><span class="pln"> x </span><span class="lit">0</span><span class="clo">)</span><span class="pln">
        </span><span class="opn">(</span><span class="kwd">begin</span><span class="pln"> </span><span class="opn">(</span><span class="pln">display </span><span class="lit">'zero</span><span class="clo">)</span><span class="pln"> </span><span class="lit">0</span><span class="clo">)</span><span class="pln">
        </span><span class="opn">(</span><span class="pun">-</span><span class="pln"> x</span><span class="clo">)))</span></pre></div>

<p>Implementing the evaluation of <code>cond</code> in this way simplifies the evaluator
because it reduces the number of special forms for which the evaluation process
must be explicitly specified.
</p>
<p>We include syntax procedures that extract the parts of a <code>cond</code>
expression, and a procedure <code>cond-&gt;if</code> that transforms <code>cond</code>
expressions into <code>if</code> expressions.  A case analysis begins with
<code>cond</code> and has a list of predicate-action clauses.  A clause is an
<code>else</code> clause if its predicate is the symbol <code>else</code>.<a class="footnote_link" id="DOCF216" href="#FOOT216"><sup>216</sup></a>
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="kwd">cond</span><span class="pun">?</span><span class="pln"> exp</span><span class="clo">)</span><span class="pln"> 
  </span><span class="opn">(</span><span class="pln">tagged-list? exp </span><span class="lit">'cond</span><span class="clo">))</span><span class="pln">
</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">cond-clauses exp</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="kwd">cdr</span><span class="pln"> exp</span><span class="clo">))</span><span class="pln">
</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">cond-else-clause? clause</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">eq</span><span class="pun">?</span><span class="pln"> </span><span class="opn">(</span><span class="pln">cond-predicate clause</span><span class="clo">)</span><span class="pln"> </span><span class="lit">'else</span><span class="clo">))</span><span class="pln">
</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">cond-predicate clause</span><span class="clo">)</span><span class="pln"> 
  </span><span class="opn">(</span><span class="kwd">car</span><span class="pln"> clause</span><span class="clo">))</span><span class="pln">
</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">cond-actions clause</span><span class="clo">)</span><span class="pln"> 
  </span><span class="opn">(</span><span class="kwd">cdr</span><span class="pln"> clause</span><span class="clo">))</span><span class="pln">
</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">cond-</span><span class="pun">&gt;</span><span class="kwd">if</span><span class="pln"> exp</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">expand-clauses </span><span class="opn">(</span><span class="pln">cond-clauses exp</span><span class="clo">)))</span><span class="pln">
</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">expand-clauses clauses</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="pln">null? clauses</span><span class="clo">)</span><span class="pln">
      </span><span class="lit">'false</span><span class="pln">     </span><span class="roman"><span class="com">; no </span><code><span class="com">else</span></code><span class="com"> clause</span></span><span class="pln">
      </span><span class="opn">(</span><span class="kwd">let</span><span class="pln"> </span><span class="opn">((</span><span class="pln">first </span><span class="opn">(</span><span class="kwd">car</span><span class="pln"> clauses</span><span class="clo">))</span><span class="pln">
            </span><span class="opn">(</span><span class="pln">rest </span><span class="opn">(</span><span class="kwd">cdr</span><span class="pln"> clauses</span><span class="clo">)))</span><span class="pln">
        </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="pln">cond-else-clause? first</span><span class="clo">)</span><span class="pln">
            </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="pln">null? rest</span><span class="clo">)</span><span class="pln">
                </span><span class="opn">(</span><span class="pln">sequence-</span><span class="pun">&gt;</span><span class="pln">exp 
                 </span><span class="opn">(</span><span class="pln">cond-actions first</span><span class="clo">))</span><span class="pln">
                </span><span class="opn">(</span><span class="err">error</span><span class="pln"> </span><span class="str">"ELSE clause isn't 
                        last: COND-&gt;IF"</span><span class="pln">
                       clauses</span><span class="clo">))</span><span class="pln">
            </span><span class="opn">(</span><span class="pln">make-if </span><span class="opn">(</span><span class="pln">cond-predicate first</span><span class="clo">)</span><span class="pln">
                     </span><span class="opn">(</span><span class="pln">sequence-</span><span class="pun">&gt;</span><span class="pln">exp 
                      </span><span class="opn">(</span><span class="pln">cond-actions first</span><span class="clo">))</span><span class="pln">
                     </span><span class="opn">(</span><span class="pln">expand-clauses 
                      rest</span><span class="clo">))))))</span></pre></div>

<p>Expressions (such as <code>cond</code>) that we choose to implement as syntactic
transformations are called <a id="index-derived-expressions"></a>
<em>derived expressions</em>.  <code>Let</code>
expressions are also derived expressions (see 
<a href="#Exercise-4_002e6">Exercise 4.6</a>).<a class="footnote_link" id="DOCF217" href="#FOOT217"><sup>217</sup></a>
</p>
<blockquote>
<p><strong><a id="Exercise-4_002e2"></a>Exercise 4.2:</strong> Louis Reasoner plans to reorder the
<code>cond</code> clauses in <code>eval</code> so that the clause for procedure
applications appears before the clause for assignments.  He argues that this
will make the interpreter more efficient: Since programs usually contain more
applications than assignments, definitions, and so on, his modified <code>eval</code>
will usually check fewer clauses than the original <code>eval</code> before
identifying the type of an expression.
</p>
<ol>
<li> What is wrong with Louis’s plan?  (Hint: What will Louis’s evaluator do with
the expression <code>(define x 3)</code>?)

</li><li> Louis is upset that his plan didn’t work.  He is willing to go to any lengths
to make his evaluator recognize procedure applications before it checks for
most other kinds of expressions.  Help him by changing the syntax of the
evaluated language so that procedure applications start with <code>call</code>.  For
example, instead of <code>(factorial 3)</code> we will now have to write <code>(call
factorial 3)</code> and instead of <code>(+ 1 2)</code> we will have to write <code>(call +
1 2)</code>.

</li></ol>
</blockquote>

<blockquote>
<p><strong><a id="Exercise-4_002e3"></a>Exercise 4.3:</strong> Rewrite <code>eval</code> so that the
dispatch is done in data-directed style.  Compare this with the data-directed
differentiation procedure of <a href="2_002e4.xhtml#Exercise-2_002e73">Exercise 2.73</a>.  (You may use the <code>car</code>
of a compound expression as the type of the expression, as is appropriate for
the syntax implemented in this section.)
</p></blockquote>

<blockquote>
<p><strong><a id="Exercise-4_002e4"></a>Exercise 4.4:</strong> Recall the definitions of the
special forms <code>and</code> and <code>or</code> from <a href="Chapter-1.xhtml#Chapter-1">Chapter 1</a>:
</p>
<ul>
<li> <code>and</code>: The expressions are evaluated from left to right.  If any
expression evaluates to false, false is returned; any remaining expressions are
not evaluated.  If all the expressions evaluate to true values, the value of
the last expression is returned.  If there are no expressions then true is
returned.

</li><li> <code>or</code>: The expressions are evaluated from left to right.  If any expression
evaluates to a true value, that value is returned; any remaining expressions
are not evaluated.  If all expressions evaluate to false, or if there are no
expressions, then false is returned.

</li></ul>

<p>Install <code>and</code> and <code>or</code> as new special forms for the evaluator by
defining appropriate syntax procedures and evaluation procedures
<code>eval-and</code> and <code>eval-or</code>.  Alternatively, show how to implement
<code>and</code> and <code>or</code> as derived expressions.
</p></blockquote>

<blockquote>
<p><strong><a id="Exercise-4_002e5"></a>Exercise 4.5:</strong> Scheme allows an additional syntax
for <code>cond</code> clauses, <code>(⟨<var>test</var>⟩ =&gt; ⟨<var>recipient</var>⟩)</code>.  If
<code>⟨</code><var>test</var><code>⟩</code> evaluates to a true value, then <code>⟨</code><var>recipient</var><code>⟩</code> is evaluated.
Its value must be a procedure of one argument; this procedure is then invoked
on the value of the <code>⟨</code><var>test</var><code>⟩</code>, and the result is returned as the value of
the <code>cond</code> expression.  For example
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">cond</span><span class="pln"> </span><span class="opn">((</span><span class="pln">assoc </span><span class="lit">'b</span><span class="pln"> </span><span class="lit">'</span><span class="opn">((</span><span class="pln">a </span><span class="lit">1</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">b </span><span class="lit">2</span><span class="clo">)))</span><span class="pln"> </span><span class="pun">=&gt;</span><span class="pln"> </span><span class="kwd">cadr</span><span class="clo">)</span><span class="pln">
      </span><span class="opn">(</span><span class="kwd">else</span><span class="pln"> false</span><span class="clo">))</span></pre></div>

<p>returns 2.  Modify the handling of <code>cond</code> so that it supports this
extended syntax.
</p></blockquote>

<blockquote>
<p><strong><a id="Exercise-4_002e6"></a>Exercise 4.6:</strong> <code>Let</code> expressions are derived
expressions, because
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">let</span><span class="pln"> </span><span class="opn">((</span><span class="pln">⟨</span><var><span class="pln">var</span><span class="pun">₁</span></var><span class="pln">⟩ ⟨</span><var><span class="pln">exp</span><span class="pun">₁</span></var><span class="pln">⟩</span><span class="clo">)</span><span class="pln"> </span><span class="roman"><span class="pun">…</span></span><span class="pln"> </span><span class="opn">(</span><span class="pln">⟨</span><var><span class="pln">var</span><span class="pun">ₙ</span></var><span class="pln">⟩ ⟨</span><var><span class="pln">exp</span><span class="pun">ₙ</span></var><span class="pln">⟩</span><span class="clo">))</span><span class="pln">
  ⟨</span><var><span class="pln">body</span></var><span class="pln">⟩</span><span class="clo">)</span></pre></div>

<p>is equivalent to
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">((</span><span class="kwd">lambda</span><span class="pln"> </span><span class="opn">(</span><span class="pln">⟨</span><var><span class="pln">var</span><span class="pun">₁</span></var><span class="pln">⟩ </span><span class="roman"><span class="pun">…</span></span><span class="pln"> ⟨</span><var><span class="pln">var</span><span class="pun">ₙ</span></var><span class="pln">⟩</span><span class="clo">)</span><span class="pln">
   ⟨</span><var><span class="pln">body</span></var><span class="pln">⟩</span><span class="clo">)</span><span class="pln">
 ⟨</span><var><span class="pln">exp</span><span class="pun">₁</span></var><span class="pln">⟩
 </span><span class="roman"><span class="pun">…</span></span><span class="pln">
 ⟨</span><var><span class="pln">exp</span><span class="pun">ₙ</span></var><span class="pln">⟩</span><span class="clo">)</span></pre></div>

<p>Implement a syntactic transformation <code>let-&gt;combination</code> that reduces
evaluating <code>let</code> expressions to evaluating combinations of the type shown
above, and add the appropriate clause to <code>eval</code> to handle <code>let</code>
expressions.
</p></blockquote>

<blockquote>
<p><strong><a id="Exercise-4_002e7"></a>Exercise 4.7:</strong> <code>Let*</code> is similar to
<code>let</code>, except that the bindings of the <code>let*</code> variables are performed
sequentially from left to right, and each binding is made in an environment in
which all of the preceding bindings are visible.  For example
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">let</span><span class="pun">*</span><span class="pln"> </span><span class="opn">((</span><span class="pln">x </span><span class="lit">3</span><span class="clo">)</span><span class="pln">
       </span><span class="opn">(</span><span class="pln">y </span><span class="opn">(</span><span class="pun">+</span><span class="pln"> x </span><span class="lit">2</span><span class="clo">))</span><span class="pln">
       </span><span class="opn">(</span><span class="pln">z </span><span class="opn">(</span><span class="pun">+</span><span class="pln"> x y </span><span class="lit">5</span><span class="clo">)))</span><span class="pln">
  </span><span class="opn">(</span><span class="pun">*</span><span class="pln"> x z</span><span class="clo">))</span></pre></div>

<p>returns 39.  Explain how a <code>let*</code> expression can be rewritten as a set of
nested <code>let</code> expressions, and write a procedure <code>let*-&gt;nested-lets</code>
that performs this transformation.  If we have already implemented <code>let</code>
(<a href="#Exercise-4_002e6">Exercise 4.6</a>) and we want to extend the evaluator to handle <code>let*</code>,
is it sufficient to add a clause to <code>eval</code> whose action is
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="pln">eval </span><span class="opn">(</span><span class="kwd">let</span><span class="pun">*-&gt;</span><span class="pln">nested-lets exp</span><span class="clo">)</span><span class="pln"> env</span><span class="clo">)</span></pre></div>

<p>or must we explicitly expand <code>let*</code> in terms of non-derived expressions?
</p></blockquote>

<blockquote>
<p><strong><a id="Exercise-4_002e8"></a>Exercise 4.8:</strong> “Named <code>let</code>” is a variant
of <code>let</code> that has the form 
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">let</span><span class="pln"> ⟨</span><var><span class="pln">var</span></var><span class="pln">⟩ ⟨</span><var><span class="pln">bindings</span></var><span class="pln">⟩ ⟨</span><var><span class="pln">body</span></var><span class="pln">⟩</span><span class="clo">)</span></pre></div>

<p>The <code>⟨</code><var>bindings</var><code>⟩</code> and <code>⟨</code><var>body</var><code>⟩</code> are just as in ordinary <code>let</code>,
except that <code>⟨</code><var>var</var><code>⟩</code> is bound within <code>⟨</code><var>body</var><code>⟩</code> to a procedure whose body
is <code>⟨</code><var>body</var><code>⟩</code> and whose parameters are the variables in the <code>⟨</code><var>bindings</var><code>⟩</code>.
Thus, one can repeatedly execute the <code>⟨</code><var>body</var><code>⟩</code> by invoking the procedure
named <code>⟨</code><var>var</var><code>⟩</code>.  For example, the iterative Fibonacci procedure 
(<a href="1_002e2.xhtml#g_t1_002e2_002e2">1.2.2</a>) can be rewritten using named <code>let</code> as follows:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">fib n</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">let</span><span class="pln"> fib-iter </span><span class="opn">((</span><span class="pln">a </span><span class="lit">1</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">b </span><span class="lit">0</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">count n</span><span class="clo">))</span><span class="pln">
    </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="pun">=</span><span class="pln"> count </span><span class="lit">0</span><span class="clo">)</span><span class="pln">
        b
        </span><span class="opn">(</span><span class="pln">fib-iter </span><span class="opn">(</span><span class="pun">+</span><span class="pln"> a b</span><span class="clo">)</span><span class="pln"> 
                  a 
                  </span><span class="opn">(</span><span class="pun">-</span><span class="pln"> count </span><span class="lit">1</span><span class="clo">)))))</span></pre></div>

<p>Modify <code>let-&gt;combination</code> of <a href="#Exercise-4_002e6">Exercise 4.6</a> to also support named
<code>let</code>.
</p></blockquote>

<blockquote>
<p><strong><a id="Exercise-4_002e9"></a>Exercise 4.9:</strong> Many languages support a variety of
iteration constructs, such as <code>do</code>, <code>for</code>, <code>while</code>, and
<code>until</code>.  In Scheme, iterative processes can be expressed in terms of
ordinary procedure calls, so special iteration constructs provide no essential
gain in computational power.  On the other hand, such constructs are often
convenient.  Design some iteration constructs, give examples of their use, and
show how to implement them as derived expressions.
</p></blockquote>

<blockquote>
<p><strong><a id="Exercise-4_002e10"></a>Exercise 4.10:</strong> By using data abstraction, we
were able to write an <code>eval</code> procedure that is independent of the
particular syntax of the language to be evaluated.  To illustrate this, design
and implement a new syntax for Scheme by modifying the procedures in this
section, without changing <code>eval</code> or <code>apply</code>.
</p></blockquote>

<a id="g_t4_002e1_002e3"></a>
<a id="Evaluator-Data-Structures"></a>
<h4 class="subsection"><span class="secnum">4.1.3</span><span class="sectitle">Evaluator Data Structures</span></h4>

<p>In addition to defining the external syntax of expressions, the evaluator
implementation must also define the data structures that the evaluator
manipulates internally, as part of the execution of a program, such as the
representation of procedures and environments and the representation of true
and false.
</p>
<a id="Testing-of-predicates"></a>
<h5 class="subsubheading">Testing of predicates</h5>

<p>For conditionals, we accept anything to be true that is not the explicit
<code>false</code> object.
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">true? x</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">not </span><span class="opn">(</span><span class="kwd">eq</span><span class="pun">?</span><span class="pln"> x false</span><span class="clo">)))</span><span class="pln">

</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">false? x</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">eq</span><span class="pun">?</span><span class="pln"> x false</span><span class="clo">))</span></pre></div>

<a id="Representing-procedures"></a>
<h5 class="subsubheading">Representing procedures</h5>

<p>To handle primitives, we assume that we have available the following
procedures:
</p>
<ul>
<li> <code>(apply-primitive-procedure ⟨<var>proc</var>⟩ ⟨<var>args</var>⟩)</code>

<p>applies the given primitive procedure to the argument values in the list
<code>⟨</code><var>args</var><code>⟩</code> and returns the result of the application.
</p>
</li><li> <code>(primitive-procedure? ⟨<var>proc</var>⟩)</code>

<p>tests whether <code>⟨</code><var>proc</var><code>⟩</code> is a primitive procedure.
</p>
</li></ul>

<p>These mechanisms for handling primitives are further described in 
<a href="#g_t4_002e1_002e4">4.1.4</a>.
</p>
<p>Compound procedures are constructed from parameters, procedure bodies, and
environments using the constructor <code>make-procedure</code>:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">make-procedure parameters body env</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">list </span><span class="lit">'procedure</span><span class="pln"> parameters body env</span><span class="clo">))</span><span class="pln">
</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">compound-procedure? p</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">tagged-list? p </span><span class="lit">'procedure</span><span class="clo">))</span><span class="pln">
</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">procedure-parameters p</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="kwd">cadr</span><span class="pln"> p</span><span class="clo">))</span><span class="pln">
</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">procedure-body p</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="kwd">caddr</span><span class="pln"> p</span><span class="clo">))</span><span class="pln">
</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">procedure-environment p</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="kwd">cadddr</span><span class="pln"> p</span><span class="clo">))</span></pre></div>

<a id="Operations-on-Environments"></a>
<h5 class="subsubheading">Operations on Environments</h5>

<p>The evaluator needs operations for manipulating environments.  As explained in
<a href="3_002e2.xhtml#g_t3_002e2">3.2</a>, an environment is a sequence of frames, where each frame is
a table of bindings that associate variables with their corresponding values.
We use the following operations for manipulating environments:
</p>
<ul>
<li> <code>(lookup-variable-value ⟨<var>var</var>⟩ ⟨<var>env</var>⟩)</code>

<p>returns the value that is bound to the symbol <code>⟨</code><var>var</var><code>⟩</code> in the environment
<code>⟨</code><var>env</var><code>⟩</code>, or signals an error if the variable is unbound.
</p>
</li><li> <code>(extend-environment ⟨<var>variables</var>⟩ ⟨<var>values</var>⟩ ⟨<var>base-env</var>⟩)</code>

<p>returns a new environment, consisting of a new frame in which the symbols in
the list <code>⟨</code><var>variables</var><code>⟩</code> are bound to the corresponding elements in the list
<code>⟨</code><var>values</var><code>⟩</code>, where the enclosing environment is the environment
<code>⟨</code><var>base-env</var><code>⟩</code>.
</p>
</li><li> <code>(define-variable! ⟨<var>var</var>⟩ ⟨<var>value</var>⟩ ⟨<var>env</var>⟩)</code>

<p>adds to the first frame in the environment <code>⟨</code><var>env</var><code>⟩</code> a new binding that
associates the variable <code>⟨</code><var>var</var><code>⟩</code> with the value <code>⟨</code><var>value</var><code>⟩</code>.
</p>
</li><li> <code>(set-variable-value! ⟨<var>var</var>⟩ ⟨<var>value</var>⟩ ⟨<var>env</var>⟩)</code>

<p>changes the binding of the variable <code>⟨</code><var>var</var><code>⟩</code> in the environment <code>⟨</code><var>env</var><code>⟩</code>
so that the variable is now bound to the value <code>⟨</code><var>value</var><code>⟩</code>, or signals an
error if the variable is unbound.
</p>
</li></ul>

<p>To implement these operations we represent an environment as a list of frames.
The enclosing environment of an environment is the <code>cdr</code> of the list.  The
empty environment is simply the empty list.
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">enclosing-environment env</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="kwd">cdr</span><span class="pln"> env</span><span class="clo">))</span><span class="pln">
</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">first-frame env</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="kwd">car</span><span class="pln"> env</span><span class="clo">))</span><span class="pln">
</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> the-empty-environment </span><span class="lit">'</span><span class="opn">(</span><span class="clo">))</span></pre></div>

<p>Each frame of an environment is represented as a pair of lists: a list of the
variables bound in that frame and a list of the associated
values.<a class="footnote_link" id="DOCF218" href="#FOOT218"><sup>218</sup></a>
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">make-frame variables values</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">cons</span><span class="pln"> variables values</span><span class="clo">))</span><span class="pln">
</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">frame-variables frame</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="kwd">car</span><span class="pln"> frame</span><span class="clo">))</span><span class="pln">
</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">frame-values frame</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="kwd">cdr</span><span class="pln"> frame</span><span class="clo">))</span><span class="pln">
</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">add-binding-to-frame! var val frame</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">set-car! frame </span><span class="opn">(</span><span class="kwd">cons</span><span class="pln"> var </span><span class="opn">(</span><span class="kwd">car</span><span class="pln"> frame</span><span class="clo">)))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">set-cdr! frame </span><span class="opn">(</span><span class="kwd">cons</span><span class="pln"> val </span><span class="opn">(</span><span class="kwd">cdr</span><span class="pln"> frame</span><span class="clo">))))</span></pre></div>

<p>To extend an environment by a new frame that associates variables with values,
we make a frame consisting of the list of variables and the list of values, and
we adjoin this to the environment.  We signal an error if the number of
variables does not match the number of values.
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">extend-environment vars vals base-env</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="pun">=</span><span class="pln"> </span><span class="opn">(</span><span class="pln">length vars</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">length vals</span><span class="clo">))</span><span class="pln">
      </span><span class="opn">(</span><span class="kwd">cons</span><span class="pln"> </span><span class="opn">(</span><span class="pln">make-frame vars vals</span><span class="clo">)</span><span class="pln"> base-env</span><span class="clo">)</span><span class="pln">
      </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="pun">&lt;</span><span class="pln"> </span><span class="opn">(</span><span class="pln">length vars</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">length vals</span><span class="clo">))</span><span class="pln">
          </span><span class="opn">(</span><span class="err">error</span><span class="pln"> </span><span class="str">"Too many arguments supplied"</span><span class="pln"> 
                 vars 
                 vals</span><span class="clo">)</span><span class="pln">
          </span><span class="opn">(</span><span class="err">error</span><span class="pln"> </span><span class="str">"Too few arguments supplied"</span><span class="pln"> 
                 vars 
                 vals</span><span class="clo">))))</span></pre></div>

<p>To look up a variable in an environment, we scan the list of variables in the
first frame.  If we find the desired variable, we return the corresponding
element in the list of values.  If we do not find the variable in the current
frame, we search the enclosing environment, and so on.  If we reach the empty
environment, we signal an “unbound variable” error.
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">lookup-variable-value var env</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">env-loop env</span><span class="clo">)</span><span class="pln">
    </span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">scan vars vals</span><span class="clo">)</span><span class="pln">
      </span><span class="opn">(</span><span class="kwd">cond</span><span class="pln"> </span><span class="opn">((</span><span class="pln">null? vars</span><span class="clo">)</span><span class="pln">
             </span><span class="opn">(</span><span class="pln">env-loop 
              </span><span class="opn">(</span><span class="pln">enclosing-environment env</span><span class="clo">)))</span><span class="pln">
            </span><span class="opn">((</span><span class="kwd">eq</span><span class="pun">?</span><span class="pln"> var </span><span class="opn">(</span><span class="kwd">car</span><span class="pln"> vars</span><span class="clo">))</span><span class="pln">
             </span><span class="opn">(</span><span class="kwd">car</span><span class="pln"> vals</span><span class="clo">))</span><span class="pln">
            </span><span class="opn">(</span><span class="kwd">else</span><span class="pln"> </span><span class="opn">(</span><span class="pln">scan </span><span class="opn">(</span><span class="kwd">cdr</span><span class="pln"> vars</span><span class="clo">)</span><span class="pln"> 
                        </span><span class="opn">(</span><span class="kwd">cdr</span><span class="pln"> vals</span><span class="clo">)))))</span><span class="pln">
    </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="kwd">eq</span><span class="pun">?</span><span class="pln"> env the-empty-environment</span><span class="clo">)</span><span class="pln">
        </span><span class="opn">(</span><span class="err">error</span><span class="pln"> </span><span class="str">"Unbound variable"</span><span class="pln"> var</span><span class="clo">)</span><span class="pln">
        </span><span class="opn">(</span><span class="kwd">let</span><span class="pln"> </span><span class="opn">((</span><span class="pln">frame </span><span class="opn">(</span><span class="pln">first-frame env</span><span class="clo">)))</span><span class="pln">
          </span><span class="opn">(</span><span class="pln">scan </span><span class="opn">(</span><span class="pln">frame-variables frame</span><span class="clo">)</span><span class="pln">
                </span><span class="opn">(</span><span class="pln">frame-values frame</span><span class="clo">)))))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">env-loop env</span><span class="clo">))</span></pre></div>

<p>To set a variable to a new value in a specified environment, we scan for the
variable, just as in <code>lookup-variable-value</code>, and change the corresponding
value when we find it.
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">set-variable-value! var val env</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">env-loop env</span><span class="clo">)</span><span class="pln">
    </span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">scan vars vals</span><span class="clo">)</span><span class="pln">
      </span><span class="opn">(</span><span class="kwd">cond</span><span class="pln"> </span><span class="opn">((</span><span class="pln">null? vars</span><span class="clo">)</span><span class="pln">
             </span><span class="opn">(</span><span class="pln">env-loop 
              </span><span class="opn">(</span><span class="pln">enclosing-environment env</span><span class="clo">)))</span><span class="pln">
            </span><span class="opn">((</span><span class="kwd">eq</span><span class="pun">?</span><span class="pln"> var </span><span class="opn">(</span><span class="kwd">car</span><span class="pln"> vars</span><span class="clo">))</span><span class="pln">
             </span><span class="opn">(</span><span class="pln">set-car! vals val</span><span class="clo">))</span><span class="pln">
            </span><span class="opn">(</span><span class="kwd">else</span><span class="pln"> </span><span class="opn">(</span><span class="pln">scan </span><span class="opn">(</span><span class="kwd">cdr</span><span class="pln"> vars</span><span class="clo">)</span><span class="pln"> 
                        </span><span class="opn">(</span><span class="kwd">cdr</span><span class="pln"> vals</span><span class="clo">)))))</span><span class="pln">
    </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="kwd">eq</span><span class="pun">?</span><span class="pln"> env the-empty-environment</span><span class="clo">)</span><span class="pln">
        </span><span class="opn">(</span><span class="err">error</span><span class="pln"> </span><span class="str">"Unbound variable: SET!"</span><span class="pln"> var</span><span class="clo">)</span><span class="pln">
        </span><span class="opn">(</span><span class="kwd">let</span><span class="pln"> </span><span class="opn">((</span><span class="pln">frame </span><span class="opn">(</span><span class="pln">first-frame env</span><span class="clo">)))</span><span class="pln">
          </span><span class="opn">(</span><span class="pln">scan </span><span class="opn">(</span><span class="pln">frame-variables frame</span><span class="clo">)</span><span class="pln">
                </span><span class="opn">(</span><span class="pln">frame-values frame</span><span class="clo">)))))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">env-loop env</span><span class="clo">))</span></pre></div>

<p>To define a variable, we search the first frame for a binding for the variable,
and change the binding if it exists (just as in <code>set-variable-value!</code>).
If no such binding exists, we adjoin one to the first frame.
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">define-variable! var val env</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">let</span><span class="pln"> </span><span class="opn">((</span><span class="pln">frame </span><span class="opn">(</span><span class="pln">first-frame env</span><span class="clo">)))</span><span class="pln">
    </span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">scan vars vals</span><span class="clo">)</span><span class="pln">
      </span><span class="opn">(</span><span class="kwd">cond</span><span class="pln"> </span><span class="opn">((</span><span class="pln">null? vars</span><span class="clo">)</span><span class="pln">
             </span><span class="opn">(</span><span class="pln">add-binding-to-frame! 
              var val frame</span><span class="clo">))</span><span class="pln">
            </span><span class="opn">((</span><span class="kwd">eq</span><span class="pun">?</span><span class="pln"> var </span><span class="opn">(</span><span class="kwd">car</span><span class="pln"> vars</span><span class="clo">))</span><span class="pln">
             </span><span class="opn">(</span><span class="pln">set-car! vals val</span><span class="clo">))</span><span class="pln">
            </span><span class="opn">(</span><span class="kwd">else</span><span class="pln"> </span><span class="opn">(</span><span class="pln">scan </span><span class="opn">(</span><span class="kwd">cdr</span><span class="pln"> vars</span><span class="clo">)</span><span class="pln"> 
                        </span><span class="opn">(</span><span class="kwd">cdr</span><span class="pln"> vals</span><span class="clo">)))))</span><span class="pln">
    </span><span class="opn">(</span><span class="pln">scan </span><span class="opn">(</span><span class="pln">frame-variables frame</span><span class="clo">)</span><span class="pln">
          </span><span class="opn">(</span><span class="pln">frame-values frame</span><span class="clo">))))</span></pre></div>

<p>The method described here is only one of many plausible ways to represent
environments.  Since we used data abstraction to isolate the rest of the
evaluator from the detailed choice of representation, we could change the
environment representation if we wanted to.  (See <a href="#Exercise-4_002e11">Exercise 4.11</a>.)  In a
production-quality Lisp system, the speed of the evaluator’s environment
operations—especially that of variable lookup—has a major impact on the
performance of the system.  The representation described here, although
conceptually simple, is not efficient and would not ordinarily be used in a
production system.<a class="footnote_link" id="DOCF219" href="#FOOT219"><sup>219</sup></a>
</p>
<blockquote>
<p><strong><a id="Exercise-4_002e11"></a>Exercise 4.11:</strong> Instead of representing a frame
as a pair of lists, we can represent a frame as a list of bindings, where each
binding is a name-value pair.  Rewrite the environment operations to use this
alternative representation.
</p></blockquote>

<blockquote>
<p><strong><a id="Exercise-4_002e12"></a>Exercise 4.12:</strong> The procedures
<code>define-variable!</code>, <code>set-variable-value!</code> and
<code>lookup-variable-value</code> can be expressed in terms of more abstract
procedures for traversing the environment structure.  Define abstractions that
capture the common patterns and redefine the three procedures in terms of these
abstractions.
</p></blockquote>

<blockquote>
<p><strong><a id="Exercise-4_002e13"></a>Exercise 4.13:</strong> Scheme allows us to create new
bindings for variables by means of <code>define</code>, but provides no way to get
rid of bindings.  Implement for the evaluator a special form
<code>make-unbound!</code> that removes the binding of a given symbol from the
environment in which the <code>make-unbound!</code> expression is evaluated.  This
problem is not completely specified.  For example, should we remove only the
binding in the first frame of the environment?  Complete the specification and
justify any choices you make.
</p></blockquote>

<a id="g_t4_002e1_002e4"></a>
<a id="Running-the-Evaluator-as-a-Program"></a>
<h4 class="subsection"><span class="secnum">4.1.4</span><span class="sectitle">Running the Evaluator as a Program</span></h4>

<p>Given the evaluator, we have in our hands a description (expressed in Lisp) of
the process by which Lisp expressions are evaluated.  One advantage of
expressing the evaluator as a program is that we can run the program.  This
gives us, running within Lisp, a working model of how Lisp itself evaluates
expressions.  This can serve as a framework for experimenting with evaluation
rules, as we shall do later in this chapter.
</p>
<p>Our evaluator program reduces expressions ultimately to the application of
primitive procedures.  Therefore, all that we need to run the evaluator is to
create a mechanism that calls on the underlying Lisp system to model the
application of primitive procedures.
</p>
<p>There must be a binding for each primitive procedure name, so that when
<code>eval</code> evaluates the operator of an application of a primitive, it will
find an object to pass to <code>apply</code>.  We thus set up a global environment
that associates unique objects with the names of the primitive procedures that
can appear in the expressions we will be evaluating.  The global environment
also includes bindings for the symbols <code>true</code> and <code>false</code>, so that
they can be used as variables in expressions to be evaluated.
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">setup-environment</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">let</span><span class="pln"> </span><span class="opn">((</span><span class="pln">initial-env
         </span><span class="opn">(</span><span class="pln">extend-environment 
          </span><span class="opn">(</span><span class="pln">primitive-procedure-names</span><span class="clo">)</span><span class="pln">
          </span><span class="opn">(</span><span class="pln">primitive-procedure-objects</span><span class="clo">)</span><span class="pln">
          the-empty-environment</span><span class="clo">)))</span><span class="pln">
    </span><span class="opn">(</span><span class="pln">define-variable! </span><span class="lit">'true</span><span class="pln"> true initial-env</span><span class="clo">)</span><span class="pln">
    </span><span class="opn">(</span><span class="pln">define-variable! </span><span class="lit">'false</span><span class="pln"> false initial-env</span><span class="clo">)</span><span class="pln">
    initial-env</span><span class="clo">))</span><span class="pln">

</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> the-global-environment 
  </span><span class="opn">(</span><span class="pln">setup-environment</span><span class="clo">))</span></pre></div>

<p>It does not matter how we represent the primitive procedure objects, so long as
<code>apply</code> can identify and apply them by using the procedures
<code>primitive-procedure?</code> and <code>apply-primitive-procedure</code>.  We have
chosen to represent a primitive procedure as a list beginning with the symbol
<code>primitive</code> and containing a procedure in the underlying Lisp that
implements that primitive.
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">primitive-procedure? proc</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">tagged-list? proc </span><span class="lit">'primitive</span><span class="clo">))</span><span class="pln">

</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">primitive-implementation proc</span><span class="clo">)</span><span class="pln"> 
  </span><span class="opn">(</span><span class="kwd">cadr</span><span class="pln"> proc</span><span class="clo">))</span></pre></div>

<p><code>Setup-environment</code> will get the primitive names and implementation
procedures from a list:<a class="footnote_link" id="DOCF220" href="#FOOT220"><sup>220</sup></a>
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> primitive-procedures
  </span><span class="opn">(</span><span class="pln">list </span><span class="opn">(</span><span class="pln">list </span><span class="lit">'car</span><span class="pln"> </span><span class="kwd">car</span><span class="clo">)</span><span class="pln">
        </span><span class="opn">(</span><span class="pln">list </span><span class="lit">'cdr</span><span class="pln"> </span><span class="kwd">cdr</span><span class="clo">)</span><span class="pln">
        </span><span class="opn">(</span><span class="pln">list </span><span class="lit">'cons</span><span class="pln"> </span><span class="kwd">cons</span><span class="clo">)</span><span class="pln">
        </span><span class="opn">(</span><span class="pln">list </span><span class="lit">'null?</span><span class="pln"> null?</span><span class="clo">)</span><span class="pln">
        ⟨</span><var><span class="pln">more primitives</span></var><span class="pln">⟩ </span><span class="clo">))</span><span class="pln">

</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">primitive-procedure-names</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">map </span><span class="kwd">car</span><span class="pln"> primitive-procedures</span><span class="clo">))</span><span class="pln">

</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">primitive-procedure-objects</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">map </span><span class="opn">(</span><span class="kwd">lambda</span><span class="pln"> </span><span class="opn">(</span><span class="pln">proc</span><span class="clo">)</span><span class="pln"> 
         </span><span class="opn">(</span><span class="pln">list </span><span class="lit">'primitive</span><span class="pln"> </span><span class="opn">(</span><span class="kwd">cadr</span><span class="pln"> proc</span><span class="clo">)))</span><span class="pln">
       primitive-procedures</span><span class="clo">))</span></pre></div>

<p>To apply a primitive procedure, we simply apply the implementation procedure to
the arguments, using the underlying Lisp
system:<a class="footnote_link" id="DOCF221" href="#FOOT221"><sup>221</sup></a>
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">apply-primitive-procedure proc args</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">apply-in-underlying-scheme
   </span><span class="opn">(</span><span class="pln">primitive-implementation proc</span><span class="clo">)</span><span class="pln"> args</span><span class="clo">))</span></pre></div>

<p>For convenience in running the metacircular evaluator, we provide a
<a id="index-driver-loop"></a>
<em>driver loop</em> that models the read-eval-print loop of the underlying
Lisp system.  It prints a <a id="index-prompt"></a>
<em>prompt</em>, reads an input expression,
evaluates this expression in the global environment, and prints the result.  We
precede each printed result by an <a id="index-output-prompt"></a>
<em>output prompt</em> so as to distinguish
the value of the expression from other output that may be printed.<a class="footnote_link" id="DOCF222" href="#FOOT222"><sup>222</sup></a>
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> input-prompt  </span><span class="str">";;; M-Eval input:"</span><span class="clo">)</span><span class="pln">
</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> output-prompt </span><span class="str">";;; M-Eval value:"</span><span class="clo">)</span><span class="pln">

</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">driver-loop</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">prompt-for-input input-prompt</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">let</span><span class="pln"> </span><span class="opn">((</span><span class="pln">input </span><span class="opn">(</span><span class="pln">read</span><span class="clo">)))</span><span class="pln">
    </span><span class="opn">(</span><span class="kwd">let</span><span class="pln"> </span><span class="opn">((</span><span class="pln">output 
           </span><span class="opn">(</span><span class="pln">eval input 
                 the-global-environment</span><span class="clo">)))</span><span class="pln">
      </span><span class="opn">(</span><span class="pln">announce-output output-prompt</span><span class="clo">)</span><span class="pln">
      </span><span class="opn">(</span><span class="pln">user-print output</span><span class="clo">)))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">driver-loop</span><span class="clo">))</span><span class="pln">

</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">prompt-for-input string</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">newline</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">newline</span><span class="clo">)</span><span class="pln"> 
  </span><span class="opn">(</span><span class="pln">display string</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">newline</span><span class="clo">))</span><span class="pln">

</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">announce-output string</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">newline</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">display string</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">newline</span><span class="clo">))</span></pre></div>

<p>We use a special printing procedure, <code>user-print</code>, to avoid printing the
environment part of a compound procedure, which may be a very long list (or may
even contain cycles).
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">user-print object</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="pln">compound-procedure? object</span><span class="clo">)</span><span class="pln">
      </span><span class="opn">(</span><span class="pln">display 
       </span><span class="opn">(</span><span class="pln">list </span><span class="lit">'compound-procedure</span><span class="pln">
             </span><span class="opn">(</span><span class="pln">procedure-parameters object</span><span class="clo">)</span><span class="pln">
             </span><span class="opn">(</span><span class="pln">procedure-body object</span><span class="clo">)</span><span class="pln">
             </span><span class="lit">'</span><span class="pun">&lt;</span><span class="pln">procedure-env</span><span class="pun">&gt;</span><span class="clo">))</span><span class="pln">
      </span><span class="opn">(</span><span class="pln">display object</span><span class="clo">)))</span></pre></div>

<p>Now all we need to do to run the evaluator is to initialize the global
environment and start the driver loop.  Here is a sample interaction:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> the-global-environment 
  </span><span class="opn">(</span><span class="pln">setup-environment</span><span class="clo">))</span><span class="pln">

</span><span class="opn">(</span><span class="pln">driver-loop</span><span class="clo">)</span><span class="pln">

</span><i><span class="com">;;; M-Eval input:</span></i><span class="pln">
</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">append x y</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="pln">null? x</span><span class="clo">)</span><span class="pln">
      y
      </span><span class="opn">(</span><span class="kwd">cons</span><span class="pln"> </span><span class="opn">(</span><span class="kwd">car</span><span class="pln"> x</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">append </span><span class="opn">(</span><span class="kwd">cdr</span><span class="pln"> x</span><span class="clo">)</span><span class="pln"> y</span><span class="clo">))))</span><span class="pln">

</span><i><span class="com">;;; M-Eval value:</span></i><span class="pln">
</span><i><span class="pln">ok</span></i><span class="pln">

</span><i><span class="com">;;; M-Eval input:</span></i><span class="pln">
</span><span class="opn">(</span><span class="pln">append </span><span class="lit">'</span><span class="opn">(</span><span class="pln">a b c</span><span class="clo">)</span><span class="pln"> </span><span class="lit">'</span><span class="opn">(</span><span class="pln">d e f</span><span class="clo">))</span><span class="pln">

</span><i><span class="com">;;; M-Eval value:</span></i><span class="pln">
</span><i><span class="opn">(</span><span class="pln">a b c d e f</span><span class="clo">)</span></i>
</pre></div>

<blockquote>
<p><strong><a id="Exercise-4_002e14"></a>Exercise 4.14:</strong> Eva Lu Ator and Louis Reasoner
are each experimenting with the metacircular evaluator.  Eva types in the
definition of <code>map</code>, and runs some test programs that use it.  They work
fine.  Louis, in contrast, has installed the system version of <code>map</code> as a
primitive for the metacircular evaluator.  When he tries it, things go terribly
wrong.  Explain why Louis’s <code>map</code> fails even though Eva’s works.
</p></blockquote>

<a id="g_t4_002e1_002e5"></a>
<a id="Data-as-Programs"></a>
<h4 class="subsection"><span class="secnum">4.1.5</span><span class="sectitle">Data as Programs</span></h4>

<p>In thinking about a Lisp program that evaluates Lisp expressions, an analogy
might be helpful.  One operational view of the meaning of a program is that a
program is a description of an abstract (perhaps infinitely large) machine.
For example, consider the familiar program to compute factorials:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">factorial n</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="pun">=</span><span class="pln"> n </span><span class="lit">1</span><span class="clo">)</span><span class="pln">
      </span><span class="lit">1</span><span class="pln">
      </span><span class="opn">(</span><span class="pun">*</span><span class="pln"> </span><span class="opn">(</span><span class="pln">factorial </span><span class="opn">(</span><span class="pun">-</span><span class="pln"> n </span><span class="lit">1</span><span class="clo">))</span><span class="pln"> n</span><span class="clo">)))</span></pre></div>

<p>We may regard this program as the description of a machine containing parts
that decrement, multiply, and test for equality, together with a two-position
switch and another factorial machine. (The factorial machine is infinite
because it contains another factorial machine within it.)  <a href="#Figure-4_002e2">Figure 4.2</a> is
a flow diagram for the factorial machine, showing how the parts are wired
together.
</p>
<figure class="float">
<a id="Figure-4_002e2"></a>
<object style="width: 54.83ex; height: 29.36ex;" data="fig/chap4/Fig4.2a.std.svg" type="image/svg+xml">SVG</object>

<figcaption class="float-caption">
<p><strong>Figure 4.2:</strong> The factorial program, viewed as an abstract machine.</p>
</figcaption>
</figure>

<p>In a similar way, we can regard the evaluator as a very special machine that
takes as input a description of a machine.  Given this input, the evaluator
configures itself to emulate the machine described.  For example, if we feed
our evaluator the definition of <code>factorial</code>, as shown in <a href="#Figure-4_002e3">Figure 4.3</a>,
the evaluator will be able to compute factorials.
</p>
<figure class="float">
<a id="Figure-4_002e3"></a>
<object style="width: 44.98ex; height: 28.32ex;" data="fig/chap4/Fig4.3.std.svg" type="image/svg+xml">SVG</object>

<figcaption class="float-caption">
<p><strong>Figure 4.3:</strong> The evaluator emulating a factorial machine.</p>
</figcaption>
</figure>

<p>From this perspective, our evaluator is seen to be a <a id="index-universal-machine"></a>
<em>universal machine</em>.  
It mimics other machines when these are described as Lisp
programs.<a class="footnote_link" id="DOCF223" href="#FOOT223"><sup>223</sup></a> This is striking. Try to imagine an analogous evaluator
for electrical circuits.  This would be a circuit that takes as input a signal
encoding the plans for some other circuit, such as a filter.  Given this input,
the circuit evaluator would then behave like a filter with the same
description.  Such a universal electrical circuit is almost unimaginably
complex.  It is remarkable that the program evaluator is a rather simple
program.<a class="footnote_link" id="DOCF224" href="#FOOT224"><sup>224</sup></a>
</p>
<p>Another striking aspect of the evaluator is that it acts as a bridge between
the data objects that are manipulated by our programming language and the
programming language itself.  Imagine that the evaluator program (implemented
in Lisp) is running, and that a user is typing expressions to the evaluator and
observing the results.  From the perspective of the user, an input expression
such as <code>(* x x)</code> is an expression in the programming language, which the
evaluator should execute.  From the perspective of the evaluator, however, the
expression is simply a list (in this case, a list of three symbols: <code>*</code>,
<code>x</code>, and <code>x</code>) that is to be manipulated according to a well-defined
set of rules.
</p>
<p>That the user’s programs are the evaluator’s data need not be a source of
confusion.  In fact, it is sometimes convenient to ignore this distinction, and
to give the user the ability to explicitly evaluate a data object as a Lisp
expression, by making <code>eval</code> available for use in programs.  Many Lisp
dialects provide a primitive <code>eval</code> procedure that takes as arguments an
expression and an environment and evaluates the expression relative to the
environment.<a class="footnote_link" id="DOCF225" href="#FOOT225"><sup>225</sup></a> Thus,
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="pln">eval </span><span class="lit">'</span><span class="opn">(</span><span class="pun">*</span><span class="pln"> </span><span class="lit">5</span><span class="pln"> </span><span class="lit">5</span><span class="clo">)</span><span class="pln"> user-initial-environment</span><span class="clo">)</span></pre></div>

<p>and
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="pln">eval </span><span class="opn">(</span><span class="kwd">cons</span><span class="pln"> </span><span class="lit">'</span><span class="pun">*</span><span class="pln"> </span><span class="opn">(</span><span class="pln">list </span><span class="lit">5</span><span class="pln"> </span><span class="lit">5</span><span class="clo">))</span><span class="pln"> 
      user-initial-environment</span><span class="clo">)</span></pre></div>

<p>will both return 25.<a class="footnote_link" id="DOCF226" href="#FOOT226"><sup>226</sup></a>
</p>
<blockquote>
<p><strong><a id="Exercise-4_002e15"></a>Exercise 4.15:</strong> Given a one-argument procedure
<code>p</code> and an object <code>a</code>, <code>p</code> is said to “halt” on <code>a</code> if
evaluating the expression <code>(p a)</code> returns a value (as opposed to
terminating with an error message or running forever).  Show that it is
impossible to write a procedure <code>halts?</code> that correctly determines whether
<code>p</code> halts on <code>a</code> for any procedure <code>p</code> and object <code>a</code>.  Use
the following reasoning: If you had such a procedure <code>halts?</code>, you could
implement the following program:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">run-forever</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">run-forever</span><span class="clo">))</span><span class="pln">

</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">try p</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="pln">halts? p p</span><span class="clo">)</span><span class="pln">
      </span><span class="opn">(</span><span class="pln">run-forever</span><span class="clo">)</span><span class="pln">
      </span><span class="lit">'halted</span><span class="clo">))</span></pre></div>

<p>Now consider evaluating the expression <code>(try try)</code> and show that any
possible outcome (either halting or running forever) violates the intended
behavior of <code>halts?</code>.<a class="footnote_link" id="DOCF227" href="#FOOT227"><sup>227</sup></a>
</p></blockquote>

<a id="g_t4_002e1_002e6"></a>
<a id="Internal-Definitions-1"></a>
<h4 class="subsection"><span class="secnum">4.1.6</span><span class="sectitle">Internal Definitions</span></h4>

<p>Our environment model of evaluation and our metacircular evaluator execute
definitions in sequence, extending the environment frame one definition at a
time.  This is particularly convenient for interactive program development, in
which the programmer needs to freely mix the application of procedures with the
definition of new procedures.  However, if we think carefully about the
internal definitions used to implement block structure (introduced in 
<a href="1_002e1.xhtml#g_t1_002e1_002e8">1.1.8</a>), we will find that name-by-name extension of the environment may
not be the best way to define local variables.
</p>
<p>Consider a procedure with internal definitions, such as
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">f x</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">even? n</span><span class="clo">)</span><span class="pln">
    </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="pun">=</span><span class="pln"> n </span><span class="lit">0</span><span class="clo">)</span><span class="pln">
        true
        </span><span class="opn">(</span><span class="pln">odd? </span><span class="opn">(</span><span class="pun">-</span><span class="pln"> n </span><span class="lit">1</span><span class="clo">))))</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">odd? n</span><span class="clo">)</span><span class="pln">
    </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="pun">=</span><span class="pln"> n </span><span class="lit">0</span><span class="clo">)</span><span class="pln">
        false
        </span><span class="opn">(</span><span class="pln">even? </span><span class="opn">(</span><span class="pun">-</span><span class="pln"> n </span><span class="lit">1</span><span class="clo">))))</span><span class="pln">
  ⟨</span><var><span class="pln">rest of body of </span><code><span class="pln">f</span></code></var><span class="pln">⟩</span><span class="clo">)</span></pre></div>

<p>Our intention here is that the name <code>odd?</code> in the body of the procedure
<code>even?</code> should refer to the procedure <code>odd?</code> that is defined after
<code>even?</code>.  The scope of the name <code>odd?</code> is the entire body of
<code>f</code>, not just the portion of the body of <code>f</code> starting at the point
where the <code>define</code> for <code>odd?</code> occurs.  Indeed, when we consider that
<code>odd?</code> is itself defined in terms of <code>even?</code>—so that <code>even?</code>
and <code>odd?</code> are mutually recursive procedures—we see that the only
satisfactory interpretation of the two <code>define</code>s is to regard them as if
the names <code>even?</code> and <code>odd?</code> were being added to the environment
simultaneously.  More generally, in block structure, the scope of a local name
is the entire procedure body in which the <code>define</code> is evaluated.
</p>
<p>As it happens, our interpreter will evaluate calls to <code>f</code> correctly, but
for an “accidental” reason: Since the definitions of the internal procedures
come first, no calls to these procedures will be evaluated until all of them
have been defined.  Hence, <code>odd?</code>  will have been defined by the time
<code>even?</code> is executed.  In fact, our sequential evaluation mechanism will
give the same result as a mechanism that directly implements simultaneous
definition for any procedure in which the internal definitions come first in a
body and evaluation of the value expressions for the defined variables doesn’t
actually use any of the defined variables.  (For an example of a procedure that
doesn’t obey these restrictions, so that sequential definition isn’t equivalent
to simultaneous definition, see <a href="#Exercise-4_002e19">Exercise 4.19</a>.)<a class="footnote_link" id="DOCF228" href="#FOOT228"><sup>228</sup></a>
</p>
<p>There is, however, a simple way to treat definitions so that internally defined
names have truly simultaneous scope—just create all local variables that will
be in the current environment before evaluating any of the value expressions.
One way to do this is by a syntax transformation on <code>lambda</code> expressions.
Before evaluating the body of a <code>lambda</code> expression, we “scan out” and
eliminate all the internal definitions in the body.  The internally defined
variables will be created with a <code>let</code> and then set to their values by
assignment.  For example, the procedure
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">lambda</span><span class="pln"> ⟨</span><var><span class="pln">vars</span></var><span class="pln">⟩
  </span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> u ⟨</span><var><span class="pln">e1</span></var><span class="pln">⟩</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> v ⟨</span><var><span class="pln">e2</span></var><span class="pln">⟩</span><span class="clo">)</span><span class="pln">
  ⟨</span><var><span class="pln">e3</span></var><span class="pln">⟩</span><span class="clo">)</span></pre></div>

<p>would be transformed into
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">lambda</span><span class="pln"> ⟨</span><var><span class="pln">vars</span></var><span class="pln">⟩
  </span><span class="opn">(</span><span class="kwd">let</span><span class="pln"> </span><span class="opn">((</span><span class="pln">u </span><span class="lit">'</span><span class="pun">*</span><span class="pln">unassigned</span><span class="pun">*</span><span class="clo">)</span><span class="pln">
        </span><span class="opn">(</span><span class="pln">v </span><span class="lit">'</span><span class="pun">*</span><span class="pln">unassigned</span><span class="pun">*</span><span class="clo">))</span><span class="pln">
    </span><span class="opn">(</span><span class="kwd">set</span><span class="pun">!</span><span class="pln"> u ⟨</span><var><span class="pln">e1</span></var><span class="pln">⟩</span><span class="clo">)</span><span class="pln">
    </span><span class="opn">(</span><span class="kwd">set</span><span class="pun">!</span><span class="pln"> v ⟨</span><var><span class="pln">e2</span></var><span class="pln">⟩</span><span class="clo">)</span><span class="pln">
    ⟨</span><var><span class="pln">e3</span></var><span class="pln">⟩</span><span class="clo">))</span></pre></div>

<p>where <code>*unassigned*</code> is a special symbol that causes looking up a variable
to signal an error if an attempt is made to use the value of the
not-yet-assigned variable.
</p>
<p>An alternative strategy for scanning out internal definitions is shown in
<a href="#Exercise-4_002e18">Exercise 4.18</a>.  Unlike the transformation shown above, this enforces the
restriction that the defined variables’ values can be evaluated without using
any of the variables’ values.<a class="footnote_link" id="DOCF229" href="#FOOT229"><sup>229</sup></a>
</p>
<blockquote>
<p><strong><a id="Exercise-4_002e16"></a>Exercise 4.16:</strong> In this exercise we implement the
method just described for interpreting internal definitions.  We assume that
the evaluator supports <code>let</code> (see <a href="#Exercise-4_002e6">Exercise 4.6</a>).
</p>
<ol>
<li> Change <code>lookup-variable-value</code> (<a href="#g_t4_002e1_002e3">4.1.3</a>) to signal an error if
the value it finds is the symbol <code>*unassigned*</code>.

</li><li> Write a procedure <code>scan-out-defines</code> that takes a procedure body and
returns an equivalent one that has no internal definitions, by making the
transformation described above.

</li><li> Install <code>scan-out-defines</code> in the interpreter, either in
<code>make-procedure</code> or in <code>procedure-body</code> (see <a href="#g_t4_002e1_002e3">4.1.3</a>).
Which place is better?  Why?

</li></ol>
</blockquote>

<blockquote>
<p><strong><a id="Exercise-4_002e17"></a>Exercise 4.17:</strong> Draw diagrams of the environment
in effect when evaluating the expression <code>⟨</code><var>e3</var><code>⟩</code> in the procedure in the
text, comparing how this will be structured when definitions are interpreted
sequentially with how it will be structured if definitions are scanned out as
described.  Why is there an extra frame in the transformed program?  Explain
why this difference in environment structure can never make a difference in the
behavior of a correct program.  Design a way to make the interpreter implement
the “simultaneous” scope rule for internal definitions without constructing
the extra frame.
</p></blockquote>

<blockquote>
<p><strong><a id="Exercise-4_002e18"></a>Exercise 4.18:</strong> Consider an alternative strategy
for scanning out definitions that translates the example in the text to
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">lambda</span><span class="pln"> ⟨</span><var><span class="pln">vars</span></var><span class="pln">⟩
  </span><span class="opn">(</span><span class="kwd">let</span><span class="pln"> </span><span class="opn">((</span><span class="pln">u </span><span class="lit">'</span><span class="pun">*</span><span class="pln">unassigned</span><span class="pun">*</span><span class="clo">)</span><span class="pln">
        </span><span class="opn">(</span><span class="pln">v </span><span class="lit">'</span><span class="pun">*</span><span class="pln">unassigned</span><span class="pun">*</span><span class="clo">))</span><span class="pln">
    </span><span class="opn">(</span><span class="kwd">let</span><span class="pln"> </span><span class="opn">((</span><span class="pln">a ⟨</span><var><span class="pln">e1</span></var><span class="pln">⟩</span><span class="clo">)</span><span class="pln">
          </span><span class="opn">(</span><span class="pln">b ⟨</span><var><span class="pln">e2</span></var><span class="pln">⟩</span><span class="clo">))</span><span class="pln">
      </span><span class="opn">(</span><span class="kwd">set</span><span class="pun">!</span><span class="pln"> u a</span><span class="clo">)</span><span class="pln">
      </span><span class="opn">(</span><span class="kwd">set</span><span class="pun">!</span><span class="pln"> v b</span><span class="clo">))</span><span class="pln">
    ⟨</span><var><span class="pln">e3</span></var><span class="pln">⟩</span><span class="clo">))</span></pre></div>

<p>Here <code>a</code> and <code>b</code> are meant to represent new variable names, created
by the interpreter, that do not appear in the user’s program.  Consider the
<code>solve</code> procedure from <a href="3_002e5.xhtml#g_t3_002e5_002e4">3.5.4</a>:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">solve f y0 dt</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> y </span><span class="opn">(</span><span class="pln">integral </span><span class="opn">(</span><span class="kwd">delay</span><span class="pln"> dy</span><span class="clo">)</span><span class="pln"> y0 dt</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> dy </span><span class="opn">(</span><span class="pln">stream-map f y</span><span class="clo">))</span><span class="pln">
  y</span><span class="clo">)</span></pre></div>

<p>Will this procedure work if internal definitions are scanned out as shown in
this exercise?  What if they are scanned out as shown in the text?  Explain.
</p></blockquote>

<blockquote>
<p><strong><a id="Exercise-4_002e19"></a>Exercise 4.19:</strong> Ben Bitdiddle, Alyssa P. Hacker,
and Eva Lu Ator are arguing about the desired result of evaluating the
expression
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">let</span><span class="pln"> </span><span class="opn">((</span><span class="pln">a </span><span class="lit">1</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">f x</span><span class="clo">)</span><span class="pln">
    </span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> b </span><span class="opn">(</span><span class="pun">+</span><span class="pln"> a x</span><span class="clo">))</span><span class="pln">
    </span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> a </span><span class="lit">5</span><span class="clo">)</span><span class="pln">
    </span><span class="opn">(</span><span class="pun">+</span><span class="pln"> a b</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">f </span><span class="lit">10</span><span class="clo">))</span></pre></div>

<p>Ben asserts that the result should be obtained using the sequential rule for
<code>define</code>: <code>b</code> is defined to be 11, then <code>a</code> is defined to be 5,
so the result is 16.  Alyssa objects that mutual recursion requires the
simultaneous scope rule for internal procedure definitions, and that it is
unreasonable to treat procedure names differently from other names.  Thus, she
argues for the mechanism implemented in <a href="#Exercise-4_002e16">Exercise 4.16</a>.  This would lead
to <code>a</code> being unassigned at the time that the value for <code>b</code> is to be
computed.  Hence, in Alyssa’s view the procedure should produce an error.  Eva
has a third opinion.  She says that if the definitions of <code>a</code> and <code>b</code>
are truly meant to be simultaneous, then the value 5 for <code>a</code> should be
used in evaluating <code>b</code>.  Hence, in Eva’s view <code>a</code> should be 5,
<code>b</code> should be 15, and the result should be 20.  Which (if any) of these
viewpoints do you support?  Can you devise a way to implement internal
definitions so that they behave as Eva prefers?<a class="footnote_link" id="DOCF230" href="#FOOT230"><sup>230</sup></a>
</p></blockquote>

<blockquote>
<p><strong><a id="Exercise-4_002e20"></a>Exercise 4.20:</strong> Because internal definitions look
sequential but are actually simultaneous, some people prefer to avoid them
entirely, and use the special form <code>letrec</code> instead.  <code>Letrec</code> looks
like <code>let</code>, so it is not surprising that the variables it binds are bound
simultaneously and have the same scope as each other.  The sample procedure
<code>f</code> above can be written without internal definitions, but with exactly
the same meaning, as
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">f x</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">letrec</span><span class="pln">
      </span><span class="opn">((</span><span class="pln">even?
        </span><span class="opn">(</span><span class="kwd">lambda</span><span class="pln"> </span><span class="opn">(</span><span class="pln">n</span><span class="clo">)</span><span class="pln">
          </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="pun">=</span><span class="pln"> n </span><span class="lit">0</span><span class="clo">)</span><span class="pln">
              true
              </span><span class="opn">(</span><span class="pln">odd? </span><span class="opn">(</span><span class="pun">-</span><span class="pln"> n </span><span class="lit">1</span><span class="clo">)))))</span><span class="pln">
       </span><span class="opn">(</span><span class="pln">odd?
        </span><span class="opn">(</span><span class="kwd">lambda</span><span class="pln"> </span><span class="opn">(</span><span class="pln">n</span><span class="clo">)</span><span class="pln">
          </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="pun">=</span><span class="pln"> n </span><span class="lit">0</span><span class="clo">)</span><span class="pln">
              false
              </span><span class="opn">(</span><span class="pln">even? </span><span class="opn">(</span><span class="pun">-</span><span class="pln"> n </span><span class="lit">1</span><span class="clo">))))))</span><span class="pln">
    ⟨</span><var><span class="pln">rest of body of </span><code><span class="pln">f</span></code></var><span class="pln">⟩</span><span class="clo">))</span></pre></div>

<p><code>Letrec</code> expressions, which have the form
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">letrec</span><span class="pln"> </span><span class="opn">((</span><span class="pln">⟨</span><var><span class="pln">var</span><span class="pun">₁</span></var><span class="pln">⟩ ⟨</span><var><span class="pln">exp</span><span class="pun">₁</span></var><span class="pln">⟩</span><span class="clo">)</span><span class="pln"> </span><span class="roman"><span class="pun">…</span></span><span class="pln"> </span><span class="opn">(</span><span class="pln">⟨</span><var><span class="pln">var</span><span class="pun">ₙ</span></var><span class="pln">⟩ ⟨</span><var><span class="pln">exp</span><span class="pun">ₙ</span></var><span class="pln">⟩</span><span class="clo">))</span><span class="pln">
  ⟨</span><var><span class="pln">body</span></var><span class="pln">⟩</span><span class="clo">)</span></pre></div>

<p>are a variation on <code>let</code> in which the expressions
<math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mo stretchy="false">⟨</mo>
    <mspace width="0.1em"/>
    <mi>e</mi>
    <mi>x</mi>
    <msub>
      <mi>p</mi>
      <mi>k</mi>
    </msub>
    <mo stretchy="false">⟩</mo>
  </mrow>
</math> that provide the initial values for the
variables <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mo stretchy="false">⟨</mo>
    <mspace width="0.06em"/>
    <mi>v</mi>
    <mi>a</mi>
    <msub>
      <mi>r</mi>
      <mi>k</mi>
    </msub>
    <mo stretchy="false">⟩</mo>
  </mrow>
</math> are evaluated in an environment
that includes all the <code>letrec</code> bindings.  This permits recursion in the
bindings, such as the mutual recursion of <code>even?</code> and <code>odd?</code> in the
example above, or the evaluation of 10 factorial with
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">letrec</span><span class="pln">
    </span><span class="opn">((</span><span class="pln">fact
      </span><span class="opn">(</span><span class="kwd">lambda</span><span class="pln"> </span><span class="opn">(</span><span class="pln">n</span><span class="clo">)</span><span class="pln">
        </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="pun">=</span><span class="pln"> n </span><span class="lit">1</span><span class="clo">)</span><span class="pln">
            </span><span class="lit">1</span><span class="pln">
            </span><span class="opn">(</span><span class="pun">*</span><span class="pln"> n </span><span class="opn">(</span><span class="pln">fact </span><span class="opn">(</span><span class="pun">-</span><span class="pln"> n </span><span class="lit">1</span><span class="clo">)))))))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">fact </span><span class="lit">10</span><span class="clo">))</span></pre></div>

<ol>
<li> Implement <code>letrec</code> as a derived expression, by transforming a
<code>letrec</code> expression into a <code>let</code> expression as shown in the text
above or in <a href="#Exercise-4_002e18">Exercise 4.18</a>.  That is, the <code>letrec</code> variables should
be created with a <code>let</code> and then be assigned their values with
<code>set!</code>.

</li><li> Louis Reasoner is confused by all this fuss about internal definitions.  The
way he sees it, if you don’t like to use <code>define</code> inside a procedure, you
can just use <code>let</code>.  Illustrate what is loose about his reasoning by
drawing an environment diagram that shows the environment in which the
<code>⟨</code><var>rest of body of <code>f</code></var><code>⟩</code> is evaluated during evaluation of the
expression <code>(f 5)</code>, with <code>f</code> defined as in this exercise.  Draw an
environment diagram for the same evaluation, but with <code>let</code> in place of
<code>letrec</code> in the definition of <code>f</code>.

</li></ol>
</blockquote>

<blockquote>
<p><strong><a id="Exercise-4_002e21"></a>Exercise 4.21:</strong> Amazingly, Louis’s intuition in
<a href="#Exercise-4_002e20">Exercise 4.20</a> is correct.  It is indeed possible to specify recursive
procedures without using <code>letrec</code> (or even <code>define</code>), although the
method for accomplishing this is much more subtle than Louis imagined.  The
following expression computes 10 factorial by applying a recursive factorial
procedure:<a class="footnote_link" id="DOCF231" href="#FOOT231"><sup>231</sup></a>
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">((</span><span class="kwd">lambda</span><span class="pln"> </span><span class="opn">(</span><span class="pln">n</span><span class="clo">)</span><span class="pln">
   </span><span class="opn">((</span><span class="kwd">lambda</span><span class="pln"> </span><span class="opn">(</span><span class="pln">fact</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">fact fact n</span><span class="clo">))</span><span class="pln">
    </span><span class="opn">(</span><span class="kwd">lambda</span><span class="pln"> </span><span class="opn">(</span><span class="pln">ft k</span><span class="clo">)</span><span class="pln">
      </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="pun">=</span><span class="pln"> k </span><span class="lit">1</span><span class="clo">)</span><span class="pln">
          </span><span class="lit">1</span><span class="pln">
          </span><span class="opn">(</span><span class="pun">*</span><span class="pln"> k </span><span class="opn">(</span><span class="pln">ft ft </span><span class="opn">(</span><span class="pun">-</span><span class="pln"> k </span><span class="lit">1</span><span class="clo">)))))))</span><span class="pln">
 </span><span class="lit">10</span><span class="clo">)</span></pre></div>

<ol>
<li> Check (by evaluating the expression) that this really does compute factorials.
Devise an analogous expression for computing Fibonacci numbers.

</li><li> Consider the following procedure, which includes mutually recursive internal
definitions:

<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">f x</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">even? n</span><span class="clo">)</span><span class="pln">
    </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="pun">=</span><span class="pln"> n </span><span class="lit">0</span><span class="clo">)</span><span class="pln">
        true
        </span><span class="opn">(</span><span class="pln">odd? </span><span class="opn">(</span><span class="pun">-</span><span class="pln"> n </span><span class="lit">1</span><span class="clo">))))</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">odd? n</span><span class="clo">)</span><span class="pln">
    </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="pun">=</span><span class="pln"> n </span><span class="lit">0</span><span class="clo">)</span><span class="pln">
        false
        </span><span class="opn">(</span><span class="pln">even? </span><span class="opn">(</span><span class="pun">-</span><span class="pln"> n </span><span class="lit">1</span><span class="clo">))))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">even? x</span><span class="clo">))</span></pre></div>

<p>Fill in the missing expressions to complete an alternative definition of
<code>f</code>, which uses neither internal definitions nor <code>letrec</code>:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">f x</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">((</span><span class="kwd">lambda</span><span class="pln"> </span><span class="opn">(</span><span class="pln">even? odd?</span><span class="clo">)</span><span class="pln">
     </span><span class="opn">(</span><span class="pln">even? even? odd? x</span><span class="clo">))</span><span class="pln">
   </span><span class="opn">(</span><span class="kwd">lambda</span><span class="pln"> </span><span class="opn">(</span><span class="pln">ev? od? n</span><span class="clo">)</span><span class="pln">
     </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="pun">=</span><span class="pln"> n </span><span class="lit">0</span><span class="clo">)</span><span class="pln"> 
         true 
         </span><span class="opn">(</span><span class="pln">od? ⟨</span><span class="pun">??</span><span class="pln">⟩ ⟨</span><span class="pun">??</span><span class="pln">⟩ ⟨</span><span class="pun">??</span><span class="pln">⟩</span><span class="clo">)))</span><span class="pln">
   </span><span class="opn">(</span><span class="kwd">lambda</span><span class="pln"> </span><span class="opn">(</span><span class="pln">ev? od? n</span><span class="clo">)</span><span class="pln">
     </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="pun">=</span><span class="pln"> n </span><span class="lit">0</span><span class="clo">)</span><span class="pln"> 
         false 
         </span><span class="opn">(</span><span class="pln">ev? ⟨</span><span class="pun">??</span><span class="pln">⟩ ⟨</span><span class="pun">??</span><span class="pln">⟩ ⟨</span><span class="pun">??</span><span class="pln">⟩</span><span class="clo">)))))</span></pre></div>
</li></ol>
</blockquote>

<a id="g_t4_002e1_002e7"></a>
<a id="Separating-Syntactic-Analysis-from-Execution"></a>
<h4 class="subsection"><span class="secnum">4.1.7</span><span class="sectitle">Separating Syntactic Analysis from Execution</span></h4>

<p>The evaluator implemented above is simple, but it is very inefficient, because
the syntactic analysis of expressions is interleaved with their execution.
Thus if a program is executed many times, its syntax is analyzed many times.
Consider, for example, evaluating <code>(factorial 4)</code> using the following
definition of <code>factorial</code>:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">factorial n</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="pun">=</span><span class="pln"> n </span><span class="lit">1</span><span class="clo">)</span><span class="pln">
      </span><span class="lit">1</span><span class="pln">
      </span><span class="opn">(</span><span class="pun">*</span><span class="pln"> </span><span class="opn">(</span><span class="pln">factorial </span><span class="opn">(</span><span class="pun">-</span><span class="pln"> n </span><span class="lit">1</span><span class="clo">))</span><span class="pln"> n</span><span class="clo">)))</span></pre></div>

<p>Each time <code>factorial</code> is called, the evaluator must determine that the
body is an <code>if</code> expression and extract the predicate.  Only then can it
evaluate the predicate and dispatch on its value.  Each time it evaluates the
expression <code>(* (factorial (- n 1)) n)</code>, or the subexpressions
<code>(factorial (- n 1))</code> and <code>(- n 1)</code>, the evaluator must perform the
case analysis in <code>eval</code> to determine that the expression is an
application, and must extract its operator and operands.  This analysis is
expensive.  Performing it repeatedly is wasteful.
</p>
<p>We can transform the evaluator to be significantly more efficient by arranging
things so that syntactic analysis is performed only once.<a class="footnote_link" id="DOCF232" href="#FOOT232"><sup>232</sup></a> We split <code>eval</code>, which takes an expression and an
environment, into two parts.  The procedure <code>analyze</code> takes only the
expression.  It performs the syntactic analysis and returns a new procedure,
the <a id="index-execution-procedure"></a>
<em>execution procedure</em>, that encapsulates the work to be done in
executing the analyzed expression.  The execution procedure takes an
environment as its argument and completes the evaluation.  This saves work
because <code>analyze</code> will be called only once on an expression, while the
execution procedure may be called many times.
</p>
<p>With the separation into analysis and execution, <code>eval</code> now becomes
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">eval exp env</span><span class="clo">)</span><span class="pln"> </span><span class="opn">((</span><span class="pln">analyze exp</span><span class="clo">)</span><span class="pln"> env</span><span class="clo">))</span></pre></div>

<p>The result of calling <code>analyze</code> is the execution procedure to be applied
to the environment.  The <code>analyze</code> procedure is the same case analysis as
performed by the original <code>eval</code> of <a href="#g_t4_002e1_002e1">4.1.1</a>, except that the
procedures to which we dispatch perform only analysis, not full evaluation:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">analyze exp</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">cond</span><span class="pln"> </span><span class="opn">((</span><span class="pln">self-evaluating? exp</span><span class="clo">)</span><span class="pln">
         </span><span class="opn">(</span><span class="pln">analyze-self-evaluating exp</span><span class="clo">))</span><span class="pln">
        </span><span class="opn">((</span><span class="pln">quoted? exp</span><span class="clo">)</span><span class="pln"> 
         </span><span class="opn">(</span><span class="pln">analyze-quoted exp</span><span class="clo">))</span><span class="pln">
        </span><span class="opn">((</span><span class="pln">variable? exp</span><span class="clo">)</span><span class="pln"> 
         </span><span class="opn">(</span><span class="pln">analyze-variable exp</span><span class="clo">))</span><span class="pln">
        </span><span class="opn">((</span><span class="pln">assignment? exp</span><span class="clo">)</span><span class="pln"> 
         </span><span class="opn">(</span><span class="pln">analyze-assignment exp</span><span class="clo">))</span><span class="pln">
        </span><span class="opn">((</span><span class="pln">definition? exp</span><span class="clo">)</span><span class="pln"> 
         </span><span class="opn">(</span><span class="pln">analyze-definition exp</span><span class="clo">))</span><span class="pln">
        </span><span class="opn">((</span><span class="kwd">if</span><span class="pun">?</span><span class="pln"> exp</span><span class="clo">)</span><span class="pln"> 
         </span><span class="opn">(</span><span class="pln">analyze-if exp</span><span class="clo">))</span><span class="pln">
        </span><span class="opn">((</span><span class="kwd">lambda</span><span class="pun">?</span><span class="pln"> exp</span><span class="clo">)</span><span class="pln"> 
         </span><span class="opn">(</span><span class="pln">analyze-lambda exp</span><span class="clo">))</span><span class="pln">
        </span><span class="opn">((</span><span class="kwd">begin</span><span class="pun">?</span><span class="pln"> exp</span><span class="clo">)</span><span class="pln"> 
         </span><span class="opn">(</span><span class="pln">analyze-sequence 
          </span><span class="opn">(</span><span class="pln">begin-actions exp</span><span class="clo">)))</span><span class="pln">
        </span><span class="opn">((</span><span class="kwd">cond</span><span class="pun">?</span><span class="pln"> exp</span><span class="clo">)</span><span class="pln"> 
         </span><span class="opn">(</span><span class="pln">analyze </span><span class="opn">(</span><span class="pln">cond-</span><span class="pun">&gt;</span><span class="kwd">if</span><span class="pln"> exp</span><span class="clo">)))</span><span class="pln">
        </span><span class="opn">((</span><span class="pln">application? exp</span><span class="clo">)</span><span class="pln"> 
         </span><span class="opn">(</span><span class="pln">analyze-application exp</span><span class="clo">))</span><span class="pln">
        </span><span class="opn">(</span><span class="kwd">else</span><span class="pln">
         </span><span class="opn">(</span><span class="err">error</span><span class="pln"> </span><span class="str">"Unknown expression 
                 type: ANALYZE"</span><span class="pln"> 
                exp</span><span class="clo">))))</span></pre></div>

<p>Here is the simplest syntactic analysis procedure, which handles
self-evaluating expressions.  It returns an execution procedure that ignores
its environment argument and just returns the expression:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">analyze-self-evaluating exp</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">lambda</span><span class="pln"> </span><span class="opn">(</span><span class="pln">env</span><span class="clo">)</span><span class="pln"> exp</span><span class="clo">))</span></pre></div>

<p>For a quoted expression, we can gain a little efficiency by extracting the text
of the quotation only once, in the analysis phase, rather than in the execution
phase.
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">analyze-quoted exp</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">let</span><span class="pln"> </span><span class="opn">((</span><span class="pln">qval </span><span class="opn">(</span><span class="pln">text-of-quotation exp</span><span class="clo">)))</span><span class="pln">
    </span><span class="opn">(</span><span class="kwd">lambda</span><span class="pln"> </span><span class="opn">(</span><span class="pln">env</span><span class="clo">)</span><span class="pln"> qval</span><span class="clo">)))</span></pre></div>

<p>Looking up a variable value must still be done in the execution phase, since
this depends upon knowing the environment.<a class="footnote_link" id="DOCF233" href="#FOOT233"><sup>233</sup></a>
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">analyze-variable exp</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">lambda</span><span class="pln"> </span><span class="opn">(</span><span class="pln">env</span><span class="clo">)</span><span class="pln"> 
    </span><span class="opn">(</span><span class="pln">lookup-variable-value exp env</span><span class="clo">)))</span></pre></div>

<p><code>Analyze-assignment</code> also must defer actually setting the variable until
the execution, when the environment has been supplied.  However, the fact that
the <code>assignment-value</code> expression can be analyzed (recursively) during
analysis is a major gain in efficiency, because the <code>assignment-value</code>
expression will now be analyzed only once.  The same holds true for
definitions.
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">analyze-assignment exp</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">let</span><span class="pln"> </span><span class="opn">((</span><span class="pln">var </span><span class="opn">(</span><span class="pln">assignment-variable exp</span><span class="clo">))</span><span class="pln">
        </span><span class="opn">(</span><span class="pln">vproc </span><span class="opn">(</span><span class="pln">analyze 
                </span><span class="opn">(</span><span class="pln">assignment-value exp</span><span class="clo">))))</span><span class="pln">
    </span><span class="opn">(</span><span class="kwd">lambda</span><span class="pln"> </span><span class="opn">(</span><span class="pln">env</span><span class="clo">)</span><span class="pln">
      </span><span class="opn">(</span><span class="pln">set-variable-value! 
       var </span><span class="opn">(</span><span class="pln">vproc env</span><span class="clo">)</span><span class="pln"> env</span><span class="clo">)</span><span class="pln">
      </span><span class="lit">'ok</span><span class="clo">)))</span><span class="pln">

</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">analyze-definition exp</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">let</span><span class="pln"> </span><span class="opn">((</span><span class="pln">var </span><span class="opn">(</span><span class="pln">definition-variable exp</span><span class="clo">))</span><span class="pln">
        </span><span class="opn">(</span><span class="pln">vproc </span><span class="opn">(</span><span class="pln">analyze 
                </span><span class="opn">(</span><span class="pln">definition-value exp</span><span class="clo">))))</span><span class="pln">
    </span><span class="opn">(</span><span class="kwd">lambda</span><span class="pln"> </span><span class="opn">(</span><span class="pln">env</span><span class="clo">)</span><span class="pln">
      </span><span class="opn">(</span><span class="pln">define-variable! var </span><span class="opn">(</span><span class="pln">vproc env</span><span class="clo">)</span><span class="pln"> env</span><span class="clo">)</span><span class="pln">
      </span><span class="lit">'ok</span><span class="clo">)))</span></pre></div>

<p>For <code>if</code> expressions, we extract and analyze the predicate, consequent,
and alternative at analysis time.
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">analyze-if exp</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">let</span><span class="pln"> </span><span class="opn">((</span><span class="pln">pproc </span><span class="opn">(</span><span class="pln">analyze </span><span class="opn">(</span><span class="pln">if-predicate exp</span><span class="clo">)))</span><span class="pln">
        </span><span class="opn">(</span><span class="pln">cproc </span><span class="opn">(</span><span class="pln">analyze </span><span class="opn">(</span><span class="pln">if-consequent exp</span><span class="clo">)))</span><span class="pln">
        </span><span class="opn">(</span><span class="pln">aproc </span><span class="opn">(</span><span class="pln">analyze </span><span class="opn">(</span><span class="pln">if-alternative exp</span><span class="clo">))))</span><span class="pln">
    </span><span class="opn">(</span><span class="kwd">lambda</span><span class="pln"> </span><span class="opn">(</span><span class="pln">env</span><span class="clo">)</span><span class="pln">
      </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="pln">true? </span><span class="opn">(</span><span class="pln">pproc env</span><span class="clo">))</span><span class="pln">
          </span><span class="opn">(</span><span class="pln">cproc env</span><span class="clo">)</span><span class="pln">
          </span><span class="opn">(</span><span class="pln">aproc env</span><span class="clo">)))))</span></pre></div>

<p>Analyzing a <code>lambda</code> expression also achieves a major gain in efficiency:
We analyze the <code>lambda</code> body only once, even though procedures resulting
from evaluation of the <code>lambda</code> may be applied many times.
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">analyze-lambda exp</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">let</span><span class="pln"> </span><span class="opn">((</span><span class="pln">vars </span><span class="opn">(</span><span class="pln">lambda-parameters exp</span><span class="clo">))</span><span class="pln">
        </span><span class="opn">(</span><span class="pln">bproc </span><span class="opn">(</span><span class="pln">analyze-sequence 
                </span><span class="opn">(</span><span class="pln">lambda-body exp</span><span class="clo">))))</span><span class="pln">
    </span><span class="opn">(</span><span class="kwd">lambda</span><span class="pln"> </span><span class="opn">(</span><span class="pln">env</span><span class="clo">)</span><span class="pln"> 
      </span><span class="opn">(</span><span class="pln">make-procedure vars bproc env</span><span class="clo">))))</span></pre></div>

<p>Analysis of a sequence of expressions (as in a <code>begin</code> or the body of a
<code>lambda</code> expression) is more involved.<a class="footnote_link" id="DOCF234" href="#FOOT234"><sup>234</sup></a> Each expression in the
sequence is analyzed, yielding an execution procedure.  These execution
procedures are combined to produce an execution procedure that takes an
environment as argument and sequentially calls each individual execution
procedure with the environment as argument.
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">analyze-sequence exps</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">sequentially proc1 proc2</span><span class="clo">)</span><span class="pln">
    </span><span class="opn">(</span><span class="kwd">lambda</span><span class="pln"> </span><span class="opn">(</span><span class="pln">env</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">proc1 env</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">proc2 env</span><span class="clo">)))</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">loop first-proc rest-procs</span><span class="clo">)</span><span class="pln">
    </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="pln">null? rest-procs</span><span class="clo">)</span><span class="pln">
        first-proc
        </span><span class="opn">(</span><span class="pln">loop </span><span class="opn">(</span><span class="pln">sequentially first-proc 
                            </span><span class="opn">(</span><span class="kwd">car</span><span class="pln"> rest-procs</span><span class="clo">))</span><span class="pln">
              </span><span class="opn">(</span><span class="kwd">cdr</span><span class="pln"> rest-procs</span><span class="clo">))))</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">let</span><span class="pln"> </span><span class="opn">((</span><span class="pln">procs </span><span class="opn">(</span><span class="pln">map analyze exps</span><span class="clo">)))</span><span class="pln">
    </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="pln">null? procs</span><span class="clo">)</span><span class="pln">
        </span><span class="opn">(</span><span class="err">error</span><span class="pln"> </span><span class="str">"Empty sequence: ANALYZE"</span><span class="clo">))</span><span class="pln">
    </span><span class="opn">(</span><span class="pln">loop </span><span class="opn">(</span><span class="kwd">car</span><span class="pln"> procs</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="kwd">cdr</span><span class="pln"> procs</span><span class="clo">))))</span></pre></div>

<p>To analyze an application, we analyze the operator and operands and construct
an execution procedure that calls the operator execution procedure (to obtain
the actual procedure to be applied) and the operand execution procedures (to
obtain the actual arguments).  We then pass these to
<code>execute-application</code>, which is the analog of <code>apply</code> in 
<a href="#g_t4_002e1_002e1">4.1.1</a>.  <code>Execute-application</code> differs from <code>apply</code> in that the
procedure body for a compound procedure has already been analyzed, so there is
no need to do further analysis.  Instead, we just call the execution procedure
for the body on the extended environment.
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">analyze-application exp</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">let</span><span class="pln"> </span><span class="opn">((</span><span class="pln">fproc </span><span class="opn">(</span><span class="pln">analyze </span><span class="opn">(</span><span class="pln">operator exp</span><span class="clo">)))</span><span class="pln">
        </span><span class="opn">(</span><span class="pln">aprocs </span><span class="opn">(</span><span class="pln">map analyze </span><span class="opn">(</span><span class="pln">operands exp</span><span class="clo">))))</span><span class="pln">
    </span><span class="opn">(</span><span class="kwd">lambda</span><span class="pln"> </span><span class="opn">(</span><span class="pln">env</span><span class="clo">)</span><span class="pln">
      </span><span class="opn">(</span><span class="pln">execute-application 
       </span><span class="opn">(</span><span class="pln">fproc env</span><span class="clo">)</span><span class="pln">
       </span><span class="opn">(</span><span class="pln">map </span><span class="opn">(</span><span class="kwd">lambda</span><span class="pln"> </span><span class="opn">(</span><span class="pln">aproc</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">aproc env</span><span class="clo">))</span><span class="pln">
            aprocs</span><span class="clo">)))))</span><span class="pln">

</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">execute-application proc args</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">cond</span><span class="pln"> </span><span class="opn">((</span><span class="pln">primitive-procedure? proc</span><span class="clo">)</span><span class="pln">
         </span><span class="opn">(</span><span class="pln">apply-primitive-procedure proc args</span><span class="clo">))</span><span class="pln">
        </span><span class="opn">((</span><span class="pln">compound-procedure? proc</span><span class="clo">)</span><span class="pln">
         </span><span class="opn">((</span><span class="pln">procedure-body proc</span><span class="clo">)</span><span class="pln">
          </span><span class="opn">(</span><span class="pln">extend-environment 
           </span><span class="opn">(</span><span class="pln">procedure-parameters proc</span><span class="clo">)</span><span class="pln">
           args
           </span><span class="opn">(</span><span class="pln">procedure-environment proc</span><span class="clo">))))</span><span class="pln">
        </span><span class="opn">(</span><span class="kwd">else</span><span class="pln"> </span><span class="opn">(</span><span class="err">error</span><span class="pln"> </span><span class="str">"Unknown procedure type: 
                      EXECUTE-APPLICATION"</span><span class="pln">
                     proc</span><span class="clo">))))</span></pre></div>

<p>Our new evaluator uses the same data structures, syntax procedures, and
run-time support procedures as in <a href="#g_t4_002e1_002e2">4.1.2</a>, <a href="#g_t4_002e1_002e3">4.1.3</a>, and
<a href="#g_t4_002e1_002e4">4.1.4</a>.
</p>
<blockquote>
<p><strong><a id="Exercise-4_002e22"></a>Exercise 4.22:</strong> Extend the evaluator in this
section to support the special form <code>let</code>.  (See <a href="#Exercise-4_002e6">Exercise 4.6</a>.)
</p></blockquote>

<blockquote>
<p><strong><a id="Exercise-4_002e23"></a>Exercise 4.23:</strong> Alyssa P. Hacker doesn’t
understand why <code>analyze-sequence</code> needs to be so complicated.  All the
other analysis procedures are straightforward transformations of the
corresponding evaluation procedures (or <code>eval</code> clauses) in 
<a href="#g_t4_002e1_002e1">4.1.1</a>.  She expected <code>analyze-sequence</code> to look like this:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">analyze-sequence exps</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">execute-sequence procs env</span><span class="clo">)</span><span class="pln">
    </span><span class="opn">(</span><span class="kwd">cond</span><span class="pln"> </span><span class="opn">((</span><span class="pln">null? </span><span class="opn">(</span><span class="kwd">cdr</span><span class="pln"> procs</span><span class="clo">))</span><span class="pln"> 
           </span><span class="opn">((</span><span class="kwd">car</span><span class="pln"> procs</span><span class="clo">)</span><span class="pln"> env</span><span class="clo">))</span><span class="pln">
          </span><span class="opn">(</span><span class="kwd">else</span><span class="pln"> </span><span class="opn">((</span><span class="kwd">car</span><span class="pln"> procs</span><span class="clo">)</span><span class="pln"> env</span><span class="clo">)</span><span class="pln">
                </span><span class="opn">(</span><span class="pln">execute-sequence 
                 </span><span class="opn">(</span><span class="kwd">cdr</span><span class="pln"> procs</span><span class="clo">)</span><span class="pln"> env</span><span class="clo">))))</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">let</span><span class="pln"> </span><span class="opn">((</span><span class="pln">procs </span><span class="opn">(</span><span class="pln">map analyze exps</span><span class="clo">)))</span><span class="pln">
    </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="pln">null? procs</span><span class="clo">)</span><span class="pln">
        </span><span class="opn">(</span><span class="err">error</span><span class="pln"> </span><span class="str">"Empty sequence: 
                ANALYZE"</span><span class="clo">))</span><span class="pln">
    </span><span class="opn">(</span><span class="kwd">lambda</span><span class="pln"> </span><span class="opn">(</span><span class="pln">env</span><span class="clo">)</span><span class="pln"> 
      </span><span class="opn">(</span><span class="pln">execute-sequence procs env</span><span class="clo">))))</span></pre></div>

<p>Eva Lu Ator explains to Alyssa that the version in the text does more of the
work of evaluating a sequence at analysis time.  Alyssa’s sequence-execution
procedure, rather than having the calls to the individual execution procedures
built in, loops through the procedures in order to call them: In effect,
although the individual expressions in the sequence have been analyzed, the
sequence itself has not been.
</p>
<p>Compare the two versions of <code>analyze-sequence</code>.  For example, consider the
common case (typical of procedure bodies) where the sequence has just one
expression.  What work will the execution procedure produced by Alyssa’s
program do?  What about the execution procedure produced by the program in the
text above?  How do the two versions compare for a sequence with two
expressions?
</p></blockquote>

<blockquote>
<p><strong><a id="Exercise-4_002e24"></a>Exercise 4.24:</strong> Design and carry out some
experiments to compare the speed of the original metacircular evaluator with
the version in this section.  Use your results to estimate the fraction of time
that is spent in analysis versus execution for various procedures.
</p></blockquote>

<div class="footnote">
<h4 class="footnotes-heading">Footnotes</h4>

<div id="FOOT207"><p><a class="footnote_backlink" href="#DOCF207"><sup>207</sup></a>
Even so, there will remain
important aspects of the evaluation process that are not elucidated by our
evaluator.  The most important of these are the detailed mechanisms by which
procedures call other procedures and return values to their callers.  We will
address these issues in <a href="Chapter-5.xhtml#Chapter-5">Chapter 5</a>, where we take a closer look at the
evaluation process by implementing the evaluator as a simple register machine.</p>
</div>
<div id="FOOT208"><p><a class="footnote_backlink" href="#DOCF208"><sup>208</sup></a>
If we grant ourselves the
ability to apply primitives, then what remains for us to implement in the
evaluator?  The job of the evaluator is not to specify the primitives of the
language, but rather to provide the connective tissue—the means of
combination and the means of abstraction—that binds a collection of
primitives to form a language. Specifically:
</p>
<ul>
<li> The evaluator enables us to deal with nested expressions.  For example,
although simply applying primitives would suffice for evaluating the expression
<code>(+ 1 6)</code>, it is not adequate for handling <code>(+ 1 (* 2 3))</code>.  As far
as the primitive procedure <code>+</code> is concerned, its arguments must be
numbers, and it would choke if we passed it the expression <code>(* 2 3)</code> as an
argument.  One important role of the evaluator is to choreograph procedure
composition so that <code>(* 2 3)</code> is reduced to 6 before being passed as an
argument to <code>+</code>.

</li><li> The evaluator allows us to use variables.  For example, the primitive procedure
for addition has no way to deal with expressions such as <code>(+ x 1)</code>.  We
need an evaluator to keep track of variables and obtain their values before
invoking the primitive procedures.

</li><li> The evaluator allows us to define compound procedures.  This involves keeping
track of procedure definitions, knowing how to use these definitions in
evaluating expressions, and providing a mechanism that enables procedures to
accept arguments.

</li><li> The evaluator provides the special forms, which must be evaluated differently
from procedure calls.

</li></ul>
</div>
<div id="FOOT209"><p><a class="footnote_backlink" href="#DOCF209"><sup>209</sup></a>
We could have simplified the <code>application?</code>
clause in <code>eval</code> by using <code>map</code> (and stipulating that <code>operands</code>
returns a list) rather than writing an explicit <code>list-of-values</code>
procedure.  We chose not to use <code>map</code> here to emphasize the fact that the
evaluator can be implemented without any use of higher-order procedures (and
thus could be written in a language that doesn’t have higher-order procedures),
even though the language that it supports will include higher-order
procedures.</p>
</div>
<div id="FOOT210"><p><a class="footnote_backlink" href="#DOCF210"><sup>210</sup></a>
In this case, the language
being implemented and the implementation language are the same.  Contemplation
of the meaning of <code>true?</code> here yields expansion of consciousness without
the abuse of substance.</p>
</div>
<div id="FOOT211"><p><a class="footnote_backlink" href="#DOCF211"><sup>211</sup></a>
This
implementation of <code>define</code> ignores a subtle issue in the handling of
internal definitions, although it works correctly in most cases.  We will see
what the problem is and how to solve it in <a href="#g_t4_002e1_002e6">4.1.6</a>.</p>
</div>
<div id="FOOT212"><p><a class="footnote_backlink" href="#DOCF212"><sup>212</sup></a>
As we said when we introduced
<code>define</code> and <code>set!</code>, these values are implementation-dependent in
Scheme—that is, the implementor can choose what value to return.</p>
</div>
<div id="FOOT213"><p><a class="footnote_backlink" href="#DOCF213"><sup>213</sup></a>
As
mentioned in <a href="2_002e3.xhtml#g_t2_002e3_002e1">2.3.1</a>, the evaluator sees a quoted expression as a
list beginning with <code>quote</code>, even if the expression is typed with the
quotation mark.  For example, the expression <code>'a</code> would be seen by the
evaluator as <code>(quote a)</code>.  See <a href="2_002e3.xhtml#Exercise-2_002e55">Exercise 2.55</a>.</p>
</div>
<div id="FOOT214"><p><a class="footnote_backlink" href="#DOCF214"><sup>214</sup></a>
The value of an <code>if</code> expression
when the predicate is false and there is no alternative is unspecified in
Scheme; we have chosen here to make it false.  We will support the use of the
variables <code>true</code> and <code>false</code> in expressions to be evaluated by
binding them in the global environment.  See <a href="#g_t4_002e1_002e4">4.1.4</a>.</p>
</div>
<div id="FOOT215"><p><a class="footnote_backlink" href="#DOCF215"><sup>215</sup></a>
These selectors for a list of expressions—and the
corresponding ones for a list of operands—are not intended as a data
abstraction.  They are introduced as mnemonic names for the basic list
operations in order to make it easier to understand the explicit-control
evaluator in <a href="5_002e4.xhtml#g_t5_002e4">5.4</a>.</p>
</div>
<div id="FOOT216"><p><a class="footnote_backlink" href="#DOCF216"><sup>216</sup></a>
The
value of a <code>cond</code> expression when all the predicates are false and there
is no <code>else</code> clause is unspecified in Scheme; we have chosen here to make
it false.</p>
</div>
<div id="FOOT217"><p><a class="footnote_backlink" href="#DOCF217"><sup>217</sup></a>
Practical Lisp systems provide a mechanism that allows a user
to add new derived expressions and specify their implementation as syntactic
transformations without modifying the evaluator.  Such a user-defined
transformation is called a <a id="index-macro"></a>
<em>macro</em>.  Although it is easy to add an
elementary mechanism for defining macros, the resulting language has subtle
name-conflict problems.  There has been much research on mechanisms for macro
definition that do not cause these difficulties.  See, for example, <a href="References.xhtml#Kohlbecker-1986">Kohlbecker 1986</a>, 
<a href="References.xhtml#Clinger-and-Rees-1991">Clinger and Rees 1991</a>, and <a href="References.xhtml#Hanson-1991">Hanson 1991</a>.</p>
</div>
<div id="FOOT218"><p><a class="footnote_backlink" href="#DOCF218"><sup>218</sup></a>
Frames are not really a data abstraction in the following
code: <code>Set-variable-value!</code> and <code>define-variable!</code> use
<code>set-car!</code>  to directly modify the values in a frame.  The purpose of the
frame procedures is to make the environment-manipulation procedures easy to
read.</p>
</div>
<div id="FOOT219"><p><a class="footnote_backlink" href="#DOCF219"><sup>219</sup></a>
The drawback of this representation (as well as the
variant in <a href="#Exercise-4_002e11">Exercise 4.11</a>) is that the evaluator may have to search
through many frames in order to find the binding for a given variable.  (Such
an approach is referred to as <a id="index-deep-binding"></a>
<em>deep binding</em>.)  One way to avoid this
inefficiency is to make use of a strategy called <a id="index-lexical-addressing"></a>
<em>lexical addressing</em>,
which will be discussed in <a href="5_002e5.xhtml#g_t5_002e5_002e6">5.5.6</a>.</p>
</div>
<div id="FOOT220"><p><a class="footnote_backlink" href="#DOCF220"><sup>220</sup></a>
Any procedure defined in the underlying Lisp
can be used as a primitive for the metacircular evaluator.  The name of a
primitive installed in the evaluator need not be the same as the name of its
implementation in the underlying Lisp; the names are the same here because the
metacircular evaluator implements Scheme itself.  Thus, for example, we could
put <code>(list 'first car)</code> or <code>(list 'square (lambda (x) (* x x)))</code> in
the list of <code>primitive-procedures</code>.</p>
</div>
<div id="FOOT221"><p><a class="footnote_backlink" href="#DOCF221"><sup>221</sup></a>
<code>Apply-in-underlying-scheme</code> is the <code>apply</code>
procedure we have used in earlier chapters.  The metacircular evaluator’s
<code>apply</code> procedure (<a href="#g_t4_002e1_002e1">4.1.1</a>) models the working of this
primitive.  Having two different things called <code>apply</code> leads to a
technical problem in running the metacircular evaluator, because defining the
metacircular evaluator’s <code>apply</code> will mask the definition of the
primitive.  One way around this is to rename the metacircular <code>apply</code> to
avoid conflict with the name of the primitive procedure.  We have assumed
instead that we have saved a reference to the underlying <code>apply</code> by doing
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> apply-in-underlying-scheme apply</span><span class="clo">)</span></pre></div>

<p>before defining the metacircular <code>apply</code>.  This allows us to access the
original version of <code>apply</code> under a different name.</p>
</div>
<div id="FOOT222"><p><a class="footnote_backlink" href="#DOCF222"><sup>222</sup></a>
The
primitive procedure <code>read</code> waits for input from the user, and returns the
next complete expression that is typed.  For example, if the user types
<code>(+ 23 x)</code>, <code>read</code> returns a three-element list containing the symbol
<code>+</code>, the number 23, and the symbol <code>x</code>.  If the user types <code>'x</code>,
<code>read</code> returns a two-element list containing the symbol <code>quote</code> and
the symbol <code>x</code>.</p>
</div>
<div id="FOOT223"><p><a class="footnote_backlink" href="#DOCF223"><sup>223</sup></a>
The fact that the machines are described in Lisp is
inessential.  If we give our evaluator a Lisp program that behaves as an
evaluator for some other language, say C, the Lisp evaluator will emulate the C
evaluator, which in turn can emulate any machine described as a C program.
Similarly, writing a Lisp evaluator in C produces a C program that can execute
any Lisp program.  The deep idea here is that any evaluator can emulate any
other.  Thus, the notion of “what can in principle be computed” (ignoring
practicalities of time and memory required) is independent of the language or
the computer, and instead reflects an underlying notion of
<a id="index-computability"></a>
<em>computability</em>.  This was first demonstrated in a clear way by Alan
M. Turing (1912-1954), whose 1936 paper laid the foundations for theoretical
computer science.  In the paper, Turing presented a simple computational
model—now known as a <a id="index-Turing-machine"></a>
<em>Turing machine</em>—and argued that any
“effective process” can be formulated as a program for such a machine.  (This
argument is known as the <a id="index-Church_002dTuring-thesis"></a>
<em>Church-Turing thesis</em>.)  Turing then
implemented a universal machine, i.e., a Turing machine that behaves as an
evaluator for Turing-machine programs.  He used this framework to demonstrate
that there are well-posed problems that cannot be computed by Turing machines
(see <a href="#Exercise-4_002e15">Exercise 4.15</a>), and so by implication cannot be formulated as
“effective processes.”  Turing went on to make fundamental contributions to
practical computer science as well.  For example, he invented the idea of
structuring programs using general-purpose subroutines.  See <a href="References.xhtml#Hodges-1983">Hodges 1983</a> for a
biography of Turing.</p>
</div>
<div id="FOOT224"><p><a class="footnote_backlink" href="#DOCF224"><sup>224</sup></a>
Some people find it counterintuitive that an evaluator, which
is implemented by a relatively simple procedure, can emulate programs that are
more complex than the evaluator itself.  The existence of a universal evaluator
machine is a deep and wonderful property of computation.  <a id="index-Recursion-theory"></a>
<em>Recursion theory</em>, 
a branch of mathematical logic, is concerned with logical limits of
computation.  Douglas Hofstadter’s beautiful book <cite>Gödel, Escher, Bach</cite>
explores some of these ideas (<a href="References.xhtml#Hofstadter-1979">Hofstadter 1979</a>).</p>
</div>
<div id="FOOT225"><p><a class="footnote_backlink" href="#DOCF225"><sup>225</sup></a>
Warning: This <code>eval</code> primitive is not identical to
the <code>eval</code> procedure we implemented in <a href="#g_t4_002e1_002e1">4.1.1</a>, because it
uses <em>actual</em> Scheme environments rather than the sample environment
structures we built in <a href="#g_t4_002e1_002e3">4.1.3</a>.  These actual environments cannot
be manipulated by the user as ordinary lists; they must be accessed via
<code>eval</code> or other special operations.  Similarly, the <code>apply</code> primitive
we saw earlier is not identical to the metacircular <code>apply</code>, because it
uses actual Scheme procedures rather than the procedure objects we constructed
in <a href="#g_t4_002e1_002e3">4.1.3</a> and <a href="#g_t4_002e1_002e4">4.1.4</a>.</p>
</div>
<div id="FOOT226"><p><a class="footnote_backlink" href="#DOCF226"><sup>226</sup></a>
The <abbr>MIT</abbr> implementation of Scheme
includes <code>eval</code>, as well as a symbol <code>user-initial-environment</code> that
is bound to the initial environment in which the user’s input expressions are
evaluated.</p>
</div>
<div id="FOOT227"><p><a class="footnote_backlink" href="#DOCF227"><sup>227</sup></a>
Although we stipulated that <code>halts?</code>
is given a procedure object, notice that this reasoning still applies even if
<code>halts?</code> can gain access to the procedure’s text and its environment.
This is Turing’s celebrated <a id="index-Halting-Theorem"></a>
<em>Halting Theorem</em>, which gave the first
clear example of a <a id="index-non_002dcomputable"></a>
<em>non-computable</em> problem, i.e., a well-posed task
that cannot be carried out as a computational procedure.</p>
</div>
<div id="FOOT228"><p><a class="footnote_backlink" href="#DOCF228"><sup>228</sup></a>
Wanting programs
to not depend on this evaluation mechanism is the reason for the “management
is not responsible” remark in <a href="1_002e1.xhtml#Footnote-28">Footnote 28</a> of <a href="Chapter-1.xhtml#Chapter-1">Chapter 1</a>.  By
insisting that internal definitions come first and do not use each other while
the definitions are being evaluated, the <abbr>IEEE</abbr> standard for Scheme
leaves implementors some choice in the mechanism used to evaluate these
definitions.  The choice of one evaluation rule rather than another here may
seem like a small issue, affecting only the interpretation of “badly formed”
programs.  However, we will see in <a href="5_002e5.xhtml#g_t5_002e5_002e6">5.5.6</a> that moving to a model
of simultaneous scoping for internal definitions avoids some nasty difficulties
that would otherwise arise in implementing a compiler.</p>
</div>
<div id="FOOT229"><p><a class="footnote_backlink" href="#DOCF229"><sup>229</sup></a>
The <abbr>IEEE</abbr> standard for Scheme
allows for different implementation strategies by specifying that it is up to
the programmer to obey this restriction, not up to the implementation to
enforce it.  Some Scheme implementations, including <abbr>MIT</abbr> Scheme, use
the transformation shown above.  Thus, some programs that don’t obey this
restriction will in fact run in such implementations.</p>
</div>
<div id="FOOT230"><p><a class="footnote_backlink" href="#DOCF230"><sup>230</sup></a>
The <abbr>MIT</abbr>
implementors of Scheme support Alyssa on the following grounds: Eva is in
principle correct—the definitions should be regarded as simultaneous.  But
it seems difficult to implement a general, efficient mechanism that does what
Eva requires.  In the absence of such a mechanism, it is better to generate an
error in the difficult cases of simultaneous definitions (Alyssa’s notion) than
to produce an incorrect answer (as Ben would have it).</p>
</div>
<div id="FOOT231"><p><a class="footnote_backlink" href="#DOCF231"><sup>231</sup></a>
This example illustrates a programming trick for
formulating recursive procedures without using <code>define</code>.  The most general
trick of this sort is the <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>Y</mi>
</math> <a id="index-operator-1"></a>
<em>operator</em>, which can be used to give a
“pure λ-calculus” implementation of recursion.  (See <a href="References.xhtml#Stoy-1977">Stoy 1977</a> for
details on the λ-calculus, and <a href="References.xhtml#Gabriel-1988">Gabriel 1988</a> for an exposition of the
<math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>Y</mi>
</math> operator in Scheme.)</p>
</div>
<div id="FOOT232"><p><a class="footnote_backlink" href="#DOCF232"><sup>232</sup></a>
This
technique is an integral part of the compilation process, which we shall
discuss in <a href="Chapter-5.xhtml#Chapter-5">Chapter 5</a>.  Jonathan Rees wrote a Scheme interpreter like this
in about 1982 for the T project (<a href="References.xhtml#Rees-and-Adams-1982">Rees and Adams 1982</a>).  Marc <a href="References.xhtml#Feeley-_00281986_0029">Feeley (1986)</a> (see
also <a href="References.xhtml#Feeley-and-Lapalme-1987">Feeley and Lapalme 1987</a>) independently invented this technique in his
master’s thesis.</p>
</div>
<div id="FOOT233"><p><a class="footnote_backlink" href="#DOCF233"><sup>233</sup></a>
There is, however, an
important part of the variable search that <em>can</em> be done as part of the
syntactic analysis.  As we will show in <a href="5_002e5.xhtml#g_t5_002e5_002e6">5.5.6</a>, one can determine
the position in the environment structure where the value of the variable will
be found, thus obviating the need to scan the environment for the entry that
matches the variable.</p>
</div>
<div id="FOOT234"><p><a class="footnote_backlink" href="#DOCF234"><sup>234</sup></a>
See <a href="#Exercise-4_002e23">Exercise 4.23</a>
for some insight into the processing of sequences.</p>
</div>
</div>
<nav class="header">
<p>
Next: <a href="4_002e2.xhtml#g_t4_002e2" accesskey="n" rel="next">4.2</a>, Prev: <a href="Chapter-4.xhtml#Chapter-4" accesskey="p" rel="prev">Chapter 4</a>, Up: <a href="#g_t4_002e1" accesskey="u" rel="prev">4.1</a>   [<a href="index.xhtml#SEC_Contents" title="Table of contents" accesskey="c" rel="contents">Contents</a>]</p>
</nav>


</section><span class="bottom jump" title="Jump to bottom"><a href="#pagebottom" accesskey="b">⇣</a></span><a id="pagebottom"></a>
</body>
</html>